The Tamed Subgradient Unadjusted Langevin Algorithm beyond Convexity

• URL: http://arxiv.org/abs/2608.06283v1
• Date: Thu, 06 Aug 2026 17:09:46 GMT
• Title: The Tamed Subgradient Unadjusted Langevin Algorithm beyond Convexity
• Abstract summary: We introduce the Subgradiented Unadjusted Langevin Algorithm (SG-TULA)<n>We derive non-asymptotic convergence bounds in Wasserstein-2 distance.<n>We provide excess risk estimates for the associated problem.
• Score: 2.676349883103404
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of sampling from target distributions whose potentials are simultaneously non-smooth, subject to superlinear gradient growth, and non-convex. We introduce the Subgradient Tamed Unadjusted Langevin Algorithm (SG-TULA), a discretisation of the Langevin diffusion that operates directly on subgradients, without relying on computationally demanding smoothing procedures. To handle the superlinear regime, taming techniques are employed to produce a stable, explicit scheme. We derive non-asymptotic convergence bounds in Wasserstein-2 distance, with all constants tracked explicitly in terms of dimension and inverse temperature, improving upon the currently known rates for subgradient-based Langevin algorithms. We further provide excess risk estimates for the associated optimisation problem. We verify the assumptions, with explicit constants, for the regularized pretraining potential of a LLM in the GPT-2 lineage and the boosted coordinate-wise variant of SG-TULA pretrains the former competitively against finetuned AdamW and Muon, for which no comparable non-asymptotic guarantees are presently available.

Related papers

• Stochastic Gradient Descent over P2 [4.6107344298094235]
  gradient descent (SGD) admits diffusion approximations that replace the complicated randomness of gradients by Gaussian noise.<n>We investigate whether an analogous approximation principle holds for optimization over probability measures, where the objective is a functional defined on the Wasserstein space P2.
  arXiv  Detail & Related papers  (2026-09-11T13:15:38Z)
• The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization [50.59470683896735]
  min-max optimization has attracted increasing attention due to its applications in modern machine learning.<n>We provide a comprehensive theoretical of gradient descent (SGDA)<n>We develop new clipping-free algorithms, i.e., Stoc-GDAM and Stoc-TRmax, and they both can achieve the optimal dependence on the target accuracy without using gradient clipping.
  arXiv  Detail & Related papers  (2026-09-05T12:49:28Z)
• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• Error estimates for tamed Euler and Randomized Euler schemes for SDEs with locally Lipschitz drift with applications to non-logconcave sampling and optimization [0.0]
  We tame the numerical discretization of differential equations with locally Lipschitz, super-optimally growing drift, and the resulting implications for sampling from non-log-concave distributions satisfying a Sobolev inequality.<n>We establish, for the first time, a non-asymotic guarantee in total variation for a tamed randomized Langevin scheme under superlinear growth.
  arXiv  Detail & Related papers  (2026-05-24T08:35:24Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  We identify the distribution of random perturbations that minimizes the estimator's variance as the perturbation stepsize tends to zero.<n>Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length.
  arXiv  Detail & Related papers  (2025-10-22T19:06:39Z)
• 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)
• Gradient-Based Non-Linear Inverse Learning [2.6149030745627644]
  We study statistical inverse learning in the context of nonlinear inverse problems under random design.<n>We employ gradient descent (GD) and descent gradient (SGD) with mini-batching, both using constant step sizes.<n>Our analysis derives convergence rates for both algorithms under classical a priori assumptions on the smoothness of the target function.
  arXiv  Detail & Related papers  (2024-12-21T22:38:17Z)
• Gradient Normalization Provably Benefits Nonconvex SGD under Heavy-Tailed Noise [60.92029979853314]
  We investigate the roles of gradient normalization and clipping in ensuring the convergence of Gradient Descent (SGD) under heavy-tailed noise. Our work provides the first theoretical evidence demonstrating the benefits of gradient normalization in SGD under heavy-tailed noise. We introduce an accelerated SGD variant incorporating gradient normalization and clipping, further enhancing convergence rates under heavy-tailed noise.
  arXiv  Detail & Related papers  (2024-10-21T22:40:42Z)
• Convergence of mean-field Langevin dynamics: Time and space discretization, stochastic gradient, and variance reduction [49.66486092259376]
  The mean-field Langevin dynamics (MFLD) is a nonlinear generalization of the Langevin dynamics that incorporates a distribution-dependent drift. Recent works have shown that MFLD globally minimizes an entropy-regularized convex functional in the space of measures. We provide a framework to prove a uniform-in-time propagation of chaos for MFLD that takes into account the errors due to finite-particle approximation, time-discretization, and gradient approximation.
  arXiv  Detail & Related papers  (2023-06-12T16:28:11Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  We study to what extent may gradient descent (SGD) be understood as a "conventional" learning rule that achieves generalization performance by obtaining a good fit training data. We analyze the closely related with-replacement SGD, for which an analogous phenomenon does not occur and prove that its population risk does in fact converge at the optimal rate.
  arXiv  Detail & Related papers  (2022-02-27T13:25:01Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Non-Convex Optimization via Non-Reversible Stochastic Gradient Langevin Dynamics [27.097121544378528]
  Gradient Langevin Dynamics (SGLD) is a powerful algorithm for optimizing a non- objective gradient. NSGLD is based on discretization of the non-reversible diffusion.
  arXiv  Detail & Related papers  (2020-04-06T17:11:03Z)
• GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values [75.17074235764757]
  We present GradientDICE for estimating the density ratio between the state distribution of the target policy and the sampling distribution. GenDICE is the state-of-the-art for estimating such density ratios.
  arXiv  Detail & Related papers  (2020-01-29T22:10:11Z)

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.