Error bounds for particle gradient descent, and extensions of the log-Sobolev and Talagrand inequalities

• URL: http://arxiv.org/abs/2403.02004v2
• Date: Thu, 11 Apr 2024 07:54:55 GMT
• Title: Error bounds for particle gradient descent, and extensions of the log-Sobolev and Talagrand inequalities
• Authors: Rocco Caprio, Juan Kuntz, Samuel Power, Adam M. Johansen,
• Abstract summary: We show that for models satisfying a condition generalizing both the log-Sobolev and the Polyak--Lojasiewicz inequalities, the flow converges exponentially fast to the set of minimizers of the free energy. We also generalize the Bakry--'Emery Theorem and show that the LSI/PLI generalization holds for models with strongly concave log-likelihoods.
• Score: 1.3124513975412255
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove non-asymptotic error bounds for particle gradient descent (PGD)~(Kuntz et al., 2023), a recently introduced algorithm for maximum likelihood estimation of large latent variable models obtained by discretizing a gradient flow of the free energy. We begin by showing that, for models satisfying a condition generalizing both the log-Sobolev and the Polyak--{\L}ojasiewicz inequalities (LSI and P{\L}I, respectively), the flow converges exponentially fast to the set of minimizers of the free energy. We achieve this by extending a result well-known in the optimal transport literature (that the LSI implies the Talagrand inequality) and its counterpart in the optimization literature (that the P{\L}I implies the so-called quadratic growth condition), and applying it to our new setting. We also generalize the Bakry--\'Emery Theorem and show that the LSI/P{\L}I generalization holds for models with strongly concave log-likelihoods. For such models, we further control PGD's discretization error, obtaining non-asymptotic error bounds. While we are motivated by the study of PGD, we believe that the inequalities and results we extend may be of independent interest.

Related papers

• Tamed Langevin sampling under weaker conditions [27.872857402255775]
  We investigate the problem of sampling from distributions that are not log-concave and are only weakly dissipative. We introduce a taming scheme which is tailored to the growth and decay properties of the target distribution. We provide explicit non-asymptotic guarantees for the proposed sampler in terms of the Kullback-Leibler divergence, total variation, and Wasserstein distance to the target distribution.
  arXiv  Detail & Related papers  (2024-05-27T23:00:40Z)
• Taming under isoperimetry [0.0]
  In this article we propose a Langevin-based scheme calledmathbfsTULA$ to sample from distributions with growing log. We derive non-asymientKL and consequently consequently satisfy a Log-Sobolev inequality.
  arXiv  Detail & Related papers  (2023-11-15T14:44:16Z)
• Convergence and concentration properties of constant step-size SGD through Markov chains [0.0]
  We consider the optimization of a smooth and strongly convex objective using constant step-size gradient descent (SGD) We show that, for unbiased gradient estimates with mildly controlled variance, the iteration converges to an invariant distribution in total variation distance. All our results are non-asymptotic and their consequences are discussed through a few applications.
  arXiv  Detail & Related papers  (2023-06-20T12:36:28Z)
• Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability [69.01076284478151]
  In machine learning optimization, gradient descent (GD) often operates at the edge of stability (EoS) This paper studies the convergence and implicit bias of constant-stepsize GD for logistic regression on linearly separable data in the EoS regime.
  arXiv  Detail & Related papers  (2023-05-19T16:24:47Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent [50.4531316289086]
  Gradient Descent (SGD) has been the method of choice for learning large-scale non-root models. An overarching paper is providing general conditions SGD converges, assuming that GF on the population loss converges. We provide a unified analysis for GD/SGD not only for classical settings like convex losses, but also for more complex problems including Retrieval Matrix sq-root.
  arXiv  Detail & Related papers  (2022-10-13T03:55:04Z)
• High-dimensional limit theorems for SGD: Effective dynamics and critical scaling [6.950316788263433]
  We prove limit theorems for the trajectories of summary statistics of gradient descent (SGD) We show a critical scaling regime for the step-size, below which the effective ballistic dynamics matches gradient flow for the population loss. About the fixed points of this effective dynamics, the corresponding diffusive limits can be quite complex and even degenerate.
  arXiv  Detail & Related papers  (2022-06-08T17:42:18Z)
• 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)
• Loss function based second-order Jensen inequality and its application to particle variational inference [112.58907653042317]
  Particle variational inference (PVI) uses an ensemble of models as an empirical approximation for the posterior distribution. PVI iteratively updates each model with a repulsion force to ensure the diversity of the optimized models. We derive a novel generalization error bound and show that it can be reduced by enhancing the diversity of models.
  arXiv  Detail & Related papers  (2021-06-09T12:13:51Z)
• Sample-efficient L0-L2 constrained structure learning of sparse Ising models [3.056751497358646]
  We consider the problem of learning the underlying graph of a sparse Ising model with $p$ nodes from $n$ i.i.d. samples. We leverage the cardinality constraint L0 norm, which is known to properly induce sparsity, and further combine it with an L2 norm to better model the non-zero coefficients.
  arXiv  Detail & Related papers  (2020-12-03T07:52:20Z)
• Probabilistic Circuits for Variational Inference in Discrete Graphical Models [101.28528515775842]
  Inference in discrete graphical models with variational methods is difficult. Many sampling-based methods have been proposed for estimating Evidence Lower Bound (ELBO) We propose a new approach that leverages the tractability of probabilistic circuit models, such as Sum Product Networks (SPN) We show that selective-SPNs are suitable as an expressive variational distribution, and prove that when the log-density of the target model is aweighted the corresponding ELBO can be computed analytically.
  arXiv  Detail & Related papers  (2020-10-22T05:04:38Z)

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.