Generalization Bounds for Heavy-Tailed SDEs through the Fractional Fokker-Planck Equation

• URL: http://arxiv.org/abs/2402.07723v2
• Date: Mon, 3 Jun 2024 14:20:34 GMT
• Title: Generalization Bounds for Heavy-Tailed SDEs through the Fractional Fokker-Planck Equation
• Authors: Benjamin Dupuis, Umut Şimşekli,
• Abstract summary: We prove high-probability bounds generalization for heavy-tailed SDEs with no nontrivial information theoretic terms. Our results suggest that heavy tails can be either beneficial or harmful depending on the problem structure.
• Score: 1.8416014644193066
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Understanding the generalization properties of heavy-tailed stochastic optimization algorithms has attracted increasing attention over the past years. While illuminating interesting aspects of stochastic optimizers by using heavy-tailed stochastic differential equations as proxies, prior works either provided expected generalization bounds, or introduced non-computable information theoretic terms. Addressing these drawbacks, in this work, we prove high-probability generalization bounds for heavy-tailed SDEs which do not contain any nontrivial information theoretic terms. To achieve this goal, we develop new proof techniques based on estimating the entropy flows associated with the so-called fractional Fokker-Planck equation (a partial differential equation that governs the evolution of the distribution of the corresponding heavy-tailed SDE). In addition to obtaining high-probability bounds, we show that our bounds have a better dependence on the dimension of parameters as compared to prior art. Our results further identify a phase transition phenomenon, which suggests that heavy tails can be either beneficial or harmful depending on the problem structure. We support our theory with experiments conducted in a variety of settings.

Related papers

• Identifying Drift, Diffusion, and Causal Structure from Temporal Snapshots [10.018568337210876]
  We present the first comprehensive approach for jointly estimating the drift and diffusion of an SDE from its temporal marginals. We show that each of these steps areAlterally optimal with respect to the Kullback-Leibler datasets.
  arXiv  Detail & Related papers  (2024-10-30T06:28:21Z)
• On Convergence Analysis of Policy Iteration Algorithms for Entropy-Regularized Stochastic Control Problems [19.742628365680353]
  We investigate the issues regarding the convergence of the Policy Iteration Algorithm(PIA) for a class of general continuous-time entropy-regularized control problems. We show that our approach can also be extended to the case when diffusion contains control, in the one dimensional setting but without much extra constraints on the coefficients.
  arXiv  Detail & Related papers  (2024-06-16T14:31:26Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Non-Parametric Learning of Stochastic Differential Equations with Non-asymptotic Fast Rates of Convergence [65.63201894457404]
  We propose a novel non-parametric learning paradigm for the identification of drift and diffusion coefficients of non-linear differential equations. The key idea essentially consists of fitting a RKHS-based approximation of the corresponding Fokker-Planck equation to such observations.
  arXiv  Detail & Related papers  (2023-05-24T20:43:47Z)
• 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)
• Generalization Properties of Stochastic Optimizers via Trajectory Analysis [48.38493838310503]
  We show that both the Fernique-Talagrand functional and the local powerlaw are predictive of generalization performance. We show that both our Fernique-Talagrand functional and the local powerlaw are predictive of generalization performance.
  arXiv  Detail & Related papers  (2021-08-02T10:58:32Z)
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks [27.54155197562196]
  We show that the trajectories of gradient descent (SGD) can be wellapproximated by a emphFeller process. We propose a "capacity metric" to measure the success of such generalizations.
  arXiv  Detail & Related papers  (2020-06-16T16:57:12Z)
• The Heavy-Tail Phenomenon in SGD [7.366405857677226]
  We show that depending on the structure of the Hessian of the loss at the minimum, the SGD iterates will converge to a emphheavy-tailed stationary distribution. We translate our results into insights about the behavior of SGD in deep learning.
  arXiv  Detail & Related papers  (2020-06-08T16:43:56Z)
• Convergence rates and approximation results for SGD and its continuous-time counterpart [16.70533901524849]
  This paper proposes a thorough theoretical analysis of convex Gradient Descent (SGD) with non-increasing step sizes. First, we show that the SGD can be provably approximated by solutions of inhomogeneous Differential Equation (SDE) using coupling. Recent analyses of deterministic and optimization methods by their continuous counterpart, we study the long-time behavior of the continuous processes at hand and non-asymptotic bounds.
  arXiv  Detail & Related papers  (2020-04-08T18:31:34Z)
• Stochastic Normalizing Flows [52.92110730286403]
  We introduce normalizing flows for maximum likelihood estimation and variational inference (VI) using differential equations (SDEs) Using the theory of rough paths, the underlying Brownian motion is treated as a latent variable and approximated, enabling efficient training of neural SDEs. These SDEs can be used for constructing efficient chains to sample from the underlying distribution of a given dataset.
  arXiv  Detail & Related papers  (2020-02-21T20:47:55Z)

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.