Differentiable Annealed Importance Sampling and the Perils of Gradient Noise

• URL: http://arxiv.org/abs/2107.10211v1
• Date: Wed, 21 Jul 2021 17:10:14 GMT
• Title: Differentiable Annealed Importance Sampling and the Perils of Gradient Noise
• Authors: Guodong Zhang, Kyle Hsu, Jianing Li, Chelsea Finn, Roger Grosse
• Abstract summary: Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
• Score: 68.44523807580438
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation, but are not fully differentiable due to the use of Metropolis-Hastings (MH) correction steps. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective using gradient-based methods. To this end, we propose a differentiable AIS algorithm by abandoning MH steps, which further unlocks mini-batch computation. We provide a detailed convergence analysis for Bayesian linear regression which goes beyond previous analyses by explicitly accounting for non-perfect transitions. Using this analysis, we prove that our algorithm is consistent in the full-batch setting and provide a sublinear convergence rate. However, we show that the algorithm is inconsistent when mini-batch gradients are used due to a fundamental incompatibility between the goals of last-iterate convergence to the posterior and elimination of the pathwise stochastic error. This result is in stark contrast to our experience with stochastic optimization and stochastic gradient Langevin dynamics, where the effects of gradient noise can be washed out by taking more steps of a smaller size. Our negative result relies crucially on our explicit consideration of convergence to the stationary distribution, and it helps explain the difficulty of developing practically effective AIS-like algorithms that exploit mini-batch gradients.

Related papers

• Robust Stochastic Optimization via Gradient Quantile Clipping [1.90365714903665]
  We introduce a quant clipping strategy for Gradient Descent (SGD) We use gradient new outliers as norm clipping chains. We propose an implementation of the algorithm using Huberiles.
  arXiv  Detail & Related papers  (2023-09-29T15:24:48Z)
• Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent [43.097493761380186]
  gradient algorithms are an efficient method of approximately solving linear systems. We show that gradient descent produces accurate predictions, even in cases where it does not converge quickly to the optimum. Experimentally, gradient descent achieves state-of-the-art performance on sufficiently large-scale or ill-conditioned regression tasks.
  arXiv  Detail & Related papers  (2023-06-20T15:07:37Z)
• 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)
• Convergence of the mini-batch SIHT algorithm [0.0]
  The Iterative Hard Thresholding (IHT) algorithm has been considered extensively as an effective deterministic algorithm for solving sparse optimizations. We show that the sequence generated by the sparse mini-batch SIHT is a supermartingale sequence and converges with probability one.
  arXiv  Detail & Related papers  (2022-09-29T03:47:46Z)
• 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)
• 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)
• Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity with bounds dependence on the confidence level that is either negative-power or logarithmic. We propose novel stepsize rules for two gradient methods with clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• Amortized variance reduction for doubly stochastic objectives [17.064916635597417]
  Approximate inference in complex probabilistic models requires optimisation of doubly objective functions. Current approaches do not take into account how mini-batchity affects samplingity, resulting in sub-optimal variance reduction. We propose a new approach in which we use a recognition network to cheaply approximate the optimal control variate for each mini-batch, with no additional gradient computations.
  arXiv  Detail & Related papers  (2020-03-09T13:23:14Z)
• Non-asymptotic bounds for stochastic optimization with biased noisy gradient oracles [8.655294504286635]
  We introduce biased gradient oracles to capture a setting where the function measurements have an estimation error. Our proposed oracles are in practical contexts, for instance, risk measure estimation from a batch of independent and identically distributed simulation.
  arXiv  Detail & Related papers  (2020-02-26T12:53:04Z)

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.