Sampling through Algorithmic Diffusion in non-convex Perceptron problems

• URL: http://arxiv.org/abs/2502.16292v1
• Date: Sat, 22 Feb 2025 16:43:01 GMT
• Title: Sampling through Algorithmic Diffusion in non-convex Perceptron problems
• Authors: Elizaveta Demyanenko, Davide Straziota, Carlo Baldassi, Carlo Lucibello,
• Abstract summary: We introduce a formalism based on the replica method to characterize the feasibility in terms of a few order parameters.<n>We show that, in the case of the perceptron problem with negative stability, approximate uniform sampling is achievable across the entire replica region.<n>In contrast, for the binary perceptron, uniform sampling via diffusion invariably fails due to the overlap gap property exhibited by the typical set of solutions.
• Score: 2.860608352191896
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We analyze the problem of sampling from the solution space of simple yet non-convex neural network models by employing a denoising diffusion process known as Algorithmic Stochastic Localization, where the score function is provided by Approximate Message Passing. We introduce a formalism based on the replica method to characterize the process in the infinite-size limit in terms of a few order parameters, and, in particular, we provide criteria for the feasibility of sampling. We show that, in the case of the spherical perceptron problem with negative stability, approximate uniform sampling is achievable across the entire replica symmetric region of the phase diagram. In contrast, for the binary perceptron, uniform sampling via diffusion invariably fails due to the overlap gap property exhibited by the typical set of solutions. We discuss the first steps in defining alternative measures that can be efficiently sampled.

Related papers

• From Denoising Score Matching to Langevin Sampling: A Fine-Grained Error Analysis in the Gaussian Setting [25.21429354164613]
  We analyze the sampling process in a simple yet representative setting using a Langevin diffusion sampler. We show that the Wasserstein sampling error can be expressed as a kernel-type norm of the data power spectrum.
  arXiv  Detail & Related papers  (2025-03-14T17:35:00Z)
• Information-Theoretic Proofs for Diffusion Sampling [13.095978794717007]
  This paper provides an elementary, self-contained analysis of diffusion-based sampling methods for generative modeling.<n>We show that, if the diffusion step sizes are chosen sufficiently small, then the sampling distribution is provably close to the target distribution.<n>Our results also provide a transparent view on how to accelerate convergence by introducing additional randomness in each step to match higher order moments in the comparison process.
  arXiv  Detail & Related papers  (2025-02-04T13:19:21Z)
• Solving High-dimensional Inverse Problems Using Amortized Likelihood-free Inference with Noisy and Incomplete Data [43.43717668587333]
  We present a likelihood-free probabilistic inversion method based on normalizing flows for high-dimensional inverse problems.<n>The proposed method is composed of two complementary networks: a summary network for data compression and an inference network for parameter estimation.<n>We apply the proposed method to an inversion problem in groundwater hydrology to estimate the posterior distribution of the log-conductivity field conditioned on spatially sparse time-series observations.
  arXiv  Detail & Related papers  (2024-12-05T19:13:17Z)
• Harmonic Path Integral Diffusion [0.4527270266697462]
  We present a novel approach for sampling from a continuous multivariate probability distribution, which may either be explicitly known (up to a normalization factor) or represented via empirical samples. Our method constructs a time-dependent bridge from a delta function centered at the origin of the state space at $t=0$, transforming it into the target distribution at $t=1$. We contrast these algorithms with other sampling methods, particularly simulated and path integral sampling, highlighting their advantages in terms of analytical control, accuracy, and computational efficiency.
  arXiv  Detail & Related papers  (2024-09-23T16:20:21Z)
• Total Uncertainty Quantification in Inverse PDE Solutions Obtained with Reduced-Order Deep Learning Surrogate Models [50.90868087591973]
  We propose an approximate Bayesian method for quantifying the total uncertainty in inverse PDE solutions obtained with machine learning surrogate models. We test the proposed framework by comparing it with the iterative ensemble smoother and deep ensembling methods for a non-linear diffusion equation.
  arXiv  Detail & Related papers  (2024-08-20T19:06:02Z)
• Amortized Posterior Sampling with Diffusion Prior Distillation [55.03585818289934]
  We propose a variational inference approach to sample from the posterior distribution for solving inverse problems. We show that our method is applicable to standard signals in Euclidean space, as well as signals on manifold.
  arXiv  Detail & Related papers  (2024-07-25T09:53:12Z)
• Solving Linear Inverse Problems Provably via Posterior Sampling with Latent Diffusion Models [98.95988351420334]
  We present the first framework to solve linear inverse problems leveraging pre-trained latent diffusion models. We theoretically analyze our algorithm showing provable sample recovery in a linear model setting.
  arXiv  Detail & Related papers  (2023-07-02T17:21:30Z)
• A Variational Perspective on Solving Inverse Problems with Diffusion Models [101.831766524264]
  Inverse tasks can be formulated as inferring a posterior distribution over data. This is however challenging in diffusion models since the nonlinear and iterative nature of the diffusion process renders the posterior intractable. We propose a variational approach that by design seeks to approximate the true posterior distribution.
  arXiv  Detail & Related papers  (2023-05-07T23:00:47Z)
• Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers [90.45898746733397]
  We develop a framework for non-asymptotic analysis of deterministic samplers used for diffusion generative modeling. We show that one step along the probability flow ODE can be expressed as two steps: 1) a restoration step that runs ascent on the conditional log-likelihood at some infinitesimally previous time, and 2) a degradation step that runs the forward process using noise pointing back towards the current gradient.
  arXiv  Detail & Related papers  (2023-03-06T18:59:19Z)
• Inverse Models for Estimating the Initial Condition of Spatio-Temporal Advection-Diffusion Processes [5.814371485767541]
  Inverse problems involve making inference about unknown parameters of a physical process using observational data. This paper investigates the estimation of the initial condition of a-temporal advection-diffusion process using spatially sparse data streams.
  arXiv  Detail & Related papers  (2023-02-08T15:30:16Z)
• SNIPS: Solving Noisy Inverse Problems Stochastically [25.567566997688044]
  We introduce a novel algorithm dubbed SNIPS, which draws samples from the posterior distribution of any linear inverse problem. Our solution incorporates ideas from Langevin dynamics and Newton's method, and exploits a pre-trained minimum mean squared error (MMSE) We show that the samples produced are sharp, detailed and consistent with the given measurements, and their diversity exposes the inherent uncertainty in the inverse problem being solved.
  arXiv  Detail & Related papers  (2021-05-31T13:33:21Z)
• Spatially Adaptive Inference with Stochastic Feature Sampling and Interpolation [72.40827239394565]
  We propose to compute features only at sparsely sampled locations. We then densely reconstruct the feature map with an efficient procedure. The presented network is experimentally shown to save substantial computation while maintaining accuracy over a variety of computer vision tasks.
  arXiv  Detail & Related papers  (2020-03-19T15:36:31Z)

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.