Non-reversible Parallel Tempering for Deep Posterior Approximation

• URL: http://arxiv.org/abs/2211.10837v1
• Date: Sun, 20 Nov 2022 01:18:40 GMT
• Title: Non-reversible Parallel Tempering for Deep Posterior Approximation
• Authors: Wei Deng, Qian Zhang, Qi Feng, Faming Liang, Guang Lin
• Abstract summary: Parallel tempering (PT), also known as replica exchange, is the go-to workhorse for simulations of multi-modal distributions. The popular deterministic even-odd (DEO) scheme exploits the non-reversibility property and has successfully reduced the communication cost from $O(P2)$ to $O(P)$ given sufficiently many $P$ chains. We generalize the DEO scheme to promote non-reversibility and propose a few solutions to tackle the underlying bias caused by the geometric stopping time.
• Score: 26.431541203372113
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Parallel tempering (PT), also known as replica exchange, is the go-to workhorse for simulations of multi-modal distributions. The key to the success of PT is to adopt efficient swap schemes. The popular deterministic even-odd (DEO) scheme exploits the non-reversibility property and has successfully reduced the communication cost from $O(P^2)$ to $O(P)$ given sufficiently many $P$ chains. However, such an innovation largely disappears in big data due to the limited chains and few bias-corrected swaps. To handle this issue, we generalize the DEO scheme to promote non-reversibility and propose a few solutions to tackle the underlying bias caused by the geometric stopping time. Notably, in big data scenarios, we obtain an appealing communication cost $O(P\log P)$ based on the optimal window size. In addition, we also adopt stochastic gradient descent (SGD) with large and constant learning rates as exploration kernels. Such a user-friendly nature enables us to conduct approximation tasks for complex posteriors without much tuning costs.

Related papers

• On the Computational Complexity of Performative Prediction [59.584063949469645]
  We show that computing an $$-performatively stable point is PPAD-complete.<n>One of our key technical contributions is to extend this PPAD-hardness result to general convex domains.
  arXiv  Detail & Related papers  (2026-01-28T02:26:35Z)
• Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels [24.314013749328677]
  We study optimal resource allocation in restless multi-armed bandits (RMABs) under unknown and non-stationary dynamics.<n>We propose a Sliding-Window Online Whittle (SW-Whittle) policy that remains computationally efficient while adapting to time-varying kernels.<n>Our algorithm consistently outperforms baselines, achieving the lowest cumulative regret across a range of non-stationary environments.
  arXiv  Detail & Related papers  (2025-06-22T22:04:52Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  We analyze the forgetting, i.e., loss on previously seen tasks, after $k$ iterations.<n>We develop novel last-iterate upper bounds in the realizable least squares setup.<n>We prove for the first time that randomization alone, with no task repetition, can prevent catastrophic in sufficiently long task sequences.
  arXiv  Detail & Related papers  (2025-04-06T18:39:45Z)
• Network reconstruction via the minimum description length principle [0.0]
  We propose an alternative nonparametric regularization scheme based on hierarchical Bayesian inference and weight quantization. Our approach follows the minimum description length (MDL) principle, and uncovers the weight distribution that allows for the most compression of the data. We demonstrate that our scheme yields systematically increased accuracy in the reconstruction of both artificial and empirical networks.
  arXiv  Detail & Related papers  (2024-05-02T05:35:09Z)
• Scalable 3D Registration via Truncated Entry-wise Absolute Residuals [65.04922801371363]
  A $3$D registration approach can process more than ten million ($107$) point pairs with over $99%$ random outliers. We call our method TEAR, as it involves minimizing an outlier-robust loss that computes Truncated Entry-wise Absolute Residuals.
  arXiv  Detail & Related papers  (2024-04-01T04:43:39Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• Resampling Stochastic Gradient Descent Cheaply for Efficient Uncertainty Quantification [6.832893024035705]
  We investigate two computationally cheap resampling-based methods to construct confidence intervals for SGD solutions. One uses multiple, but few, SGDs in parallel via resampling with replacement from the data, and another operates this in an online fashion.
  arXiv  Detail & Related papers  (2023-10-17T08:18:10Z)
• Differentiating Through Integer Linear Programs with Quadratic Regularization and Davis-Yin Splitting [5.199570417938866]
  We study the case where the problem in question is an Linear Program (ILP) We prove that the resulting scheme is compatible with the recently introduced Jacobian-free backpropagation (JFB) Our experiments on two representative ILPs, the shortest path problem and the knapsack problem, demonstrate that this combination-DYS on the forward pass, JFB on the backward pass-yields a scheme which scales more effectively to high-dimensional problems than existing schemes.
  arXiv  Detail & Related papers  (2023-01-31T04:03:28Z)
• Scaling up Stochastic Gradient Descent for Non-convex Optimisation [5.908471365011942]
  We propose a novel approach to the problem of shared parallel computation. By combining two strategies into a unified framework, DPSGD is a better trade computation framework. The potential gains can be achieved by DPSGD on a deep learning (DRL) problem (Latent Diletrichal inference) and on a deep learning (DRL) problem (advantage actor - A2C)
  arXiv  Detail & Related papers  (2022-10-06T13:06:08Z)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  We propose a novel offline reinforcement learning algorithm called Pessimistic vAlue iteRaTion with rEward Decomposition (PARTED) PARTED decomposes the trajectory return into per-step proxy rewards via least-squares-based reward redistribution, and then performs pessimistic value based on the learned proxy reward. To the best of our knowledge, PARTED is the first offline RL algorithm that is provably efficient in general MDP with trajectory-wise reward.
  arXiv  Detail & Related papers  (2022-06-13T19:11:22Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning. The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
  arXiv  Detail & Related papers  (2021-10-09T21:13:48Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large scale feature selection problems. We test our methods on problems with $p$ as large as $500,000$.
  arXiv  Detail & Related papers  (2020-06-15T21:55:34Z)

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.