kTULA: A Langevin sampling algorithm with improved KL bounds under super-linear log-gradients

• URL: http://arxiv.org/abs/2506.04878v1
• Date: Thu, 05 Jun 2025 10:51:18 GMT
• Title: kTULA: A Langevin sampling algorithm with improved KL bounds under super-linear log-gradients
• Authors: Iosif Lytras, Sotirios Sabanis, Ying Zhang,
• Abstract summary: We propose a tamed Langevin dynamics-based algorithm, called kTULA, to solve the problem of sampling from distributions with super-linearly growing log-gradients.<n>We show that our main results can be used to provide theoretical guarantees for the performance of kTULA.
• Score: 4.200092006696932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by applications in deep learning, where the global Lipschitz continuity condition is often not satisfied, we examine the problem of sampling from distributions with super-linearly growing log-gradients. We propose a novel tamed Langevin dynamics-based algorithm, called kTULA, to solve the aforementioned sampling problem, and provide a theoretical guarantee for its performance. More precisely, we establish a non-asymptotic convergence bound in Kullback-Leibler (KL) divergence with the best-known rate of convergence equal to $2-\overline{\epsilon}$, $\overline{\epsilon}>0$, which significantly improves relevant results in existing literature. This enables us to obtain an improved non-asymptotic error bound in Wasserstein-2 distance, which can be used to further derive a non-asymptotic guarantee for kTULA to solve the associated optimization problems. To illustrate the applicability of kTULA, we apply the proposed algorithm to the problem of sampling from a high-dimensional double-well potential distribution and to an optimization problem involving a neural network. We show that our main results can be used to provide theoretical guarantees for the performance of kTULA.

Related papers

• The Performance Of The Unadjusted Langevin Algorithm Without Smoothness Assumptions [0.0]
  We propose a Langevin-based algorithm that does not rely on popular but computationally challenging techniques.<n>We show that the performance of samplers like ULA does not necessarily degenerate arbitrarily with low regularity.
  arXiv  Detail & Related papers  (2025-02-05T18:55:54Z)
• Distributionally Robust Optimization via Iterative Algorithms in Continuous Probability Spaces [6.992239210938067]
  We consider a minimax problem motivated by distributionally robust optimization (DRO) when the worst-case distribution is continuous.<n>Recent research has explored learning the worst-case distribution using neural network-based generative networks.<n>This paper bridges this theoretical challenge by presenting an iterative algorithm to solve such a minimax problem.
  arXiv  Detail & Related papers  (2024-12-29T19:31:23Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning [45.78238792836363]
  We present a single-loop algorithm named SLEDGE (Single-Loop-E Gradient Estimator) for periodic convergence. Unlike existing methods, SLEDGE has the advantage of versatility; (ii) second-order optimal, (ii) in the PL region, and (iii) smaller complexity under less of data.
  arXiv  Detail & Related papers  (2022-09-01T11:05:26Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Non-asymptotic estimates for TUSLA algorithm for non-convex learning with applications to neural networks with ReLU activation function [3.5044892799305956]
  We provide a non-asymptotic analysis for the tamed un-adjusted Langevin algorithm (TUSLA) introduced in Lovas et al. In particular, we establish non-asymptotic error bounds for the TUSLA algorithm in Wassersteinstein-1-2. We show that the TUSLA algorithm converges rapidly to the optimal solution.
  arXiv  Detail & Related papers  (2021-07-19T07:13:02Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  We study the problem of solving strongly convex and smooth unconstrained optimization problems using first-order algorithms. We devise a novel, referred to as Recursive One-Over-T SGD, based on an easily implementable, averaging of past gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an sense.
  arXiv  Detail & Related papers  (2020-08-28T14:46:56Z)
• 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)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

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.