Global Well-posedness and Convergence Analysis of Score-based Generative Models via Sharp Lipschitz Estimates

• URL: http://arxiv.org/abs/2405.16104v1
• Date: Sat, 25 May 2024 07:31:24 GMT
• Title: Global Well-posedness and Convergence Analysis of Score-based Generative Models via Sharp Lipschitz Estimates
• Authors: Connor Mooney, Zhongjian Wang, Jack Xin, Yifeng Yu,
• Abstract summary: We establish global well-posedness and convergence of the score-based generative models (SGM) For the smooth case, we start from a Lipschitz bound of the score function with optimal time length. The optimality is validated by an example whose Lipschitz constant of scores is bounded at initial but blows up in finite time.
• Score: 1.3124513975412255
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We establish global well-posedness and convergence of the score-based generative models (SGM) under minimal general assumptions of initial data for score estimation. For the smooth case, we start from a Lipschitz bound of the score function with optimal time length. The optimality is validated by an example whose Lipschitz constant of scores is bounded at initial but blows up in finite time. This necessitates the separation of time scales in conventional bounds for non-log-concave distributions. In contrast, our follow up analysis only relies on a local Lipschitz condition and is valid globally in time. This leads to the convergence of numerical scheme without time separation. For the non-smooth case, we show that the optimal Lipschitz bound is O(1/t) in the point-wise sense for distributions supported on a compact, smooth and low-dimensional manifold with boundary.

Related papers

• Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions [19.008521454738425]
  We study the problem of differentially private convex optimization (DP-SCO) with heavy-tailed gradients, where we assume a $ktextth$-moment bound on the Lipschitz constants of sample functions rather than a uniform bound. We propose a new reduction-based approach that enables us to obtain the first optimal rates (up to logarithmic factors) in the heavy-tailed setting, achieving error $Gcdot frac 1 sqrt n + G_k cdot (fracsqrt dnepsilon)1
  arXiv  Detail & Related papers  (2024-06-04T21:26:29Z)
• Optimal score estimation via empirical Bayes smoothing [13.685846094715364]
  We study the problem of estimating the score function of an unknown probability distribution $rho*$ from $n$ independent and identically distributed observations in $d$ dimensions. We show that a regularized score estimator based on a Gaussian kernel attains this rate, shown optimal by a matching minimax lower bound.
  arXiv  Detail & Related papers  (2024-02-12T16:17:40Z)
• Stochastic Weakly Convex Optimization Beyond Lipschitz Continuity [5.866816093792934]
  We show that a wide class of continuity algorithms, including the subgradient method, preserve the $mathO convergence rate with constant failure rate. Our analyses rest on rather weak assumptions: the Lipschitz parameter can be either bounded by a general growth function of $|x|$ or locally estimated through independent random samples.
  arXiv  Detail & Related papers  (2024-01-25T06:06:31Z)
• KL Convergence Guarantees for Score diffusion models under minimal data assumptions [9.618473763561418]
  A notable challenge persists in the form of a lack of comprehensive quantitative results. This article focuses on score diffusion models with fixed step size stemming from the Ornstein-Uhlenbeck semigroup and its kinetic counterpart.
  arXiv  Detail & Related papers  (2023-08-23T16:31:08Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• Beyond Uniform Lipschitz Condition in Differentially Private Optimization [28.04430869054056]
  Most prior results on differentially private gradient descent (DP-SGD) are derived under the simplistic assumption of uniform Lipschitzness, i.e., the per-sample gradient is uniformly uniform. We provide principled guidance choosing the norm over-dependent in our general version of Lipschitzness when the per-sample Lipschitz constants are bounded.
  arXiv  Detail & Related papers  (2022-06-21T20:11:30Z)
• 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)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)
• SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
  We consider the RandomShuffle (shuffle at the beginning of each epoch) and SingleShuffle (shuffle only once) We establish minimax optimal convergence rates of these algorithms up to poly-log factor gaps. We further sharpen the tight convergence results for RandomShuffle by removing the drawbacks common to all prior arts.
  arXiv  Detail & Related papers  (2020-06-12T05:00:44Z)
• Exactly Computing the Local Lipschitz Constant of ReLU Networks [98.43114280459271]
  The local Lipschitz constant of a neural network is a useful metric for robustness, generalization, and fairness evaluation. We show strong inapproximability results for estimating Lipschitz constants of ReLU networks. We leverage this algorithm to evaluate the tightness of competing Lipschitz estimators and the effects of regularized training on the Lipschitz constant.
  arXiv  Detail & Related papers  (2020-03-02T22:15:54Z)

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.