An official website of the United States government
Markov chain Monte Carlo (MCMC) methods generate samples that are asymptotically distributed from a target distribution of interest as the number of iterations goes to infinity. Various theoretical results provide upper bounds on the distance between the target and marginal distribution after a fixed number of iterations. These upper bounds are on a case by case basis and typically involve intractable quantities, which limits their use for practitioners. We introduce L-lag couplings to generate computable, non-asymptotic upper bound estimates for the total variation or the Wasserstein distance of general Markov chains. We apply L-lag couplings to the tasks of (i) determining MCMC burn-in, (ii) comparing different MCMC algorithms with the same target, and (iii) comparing exact and approximate MCMC. Lastly, we (iv) assess the bias of sequential Monte Carlo and self-normalized importance samplers.
more »
« less
Maximal Couplings of the Metropolis-Hastings Algorithm
Couplings play a central role in the analysis of Markov chain Monte Carlo algorithms and appear increasingly often in the algorithms themselves, e.g. in convergence diagnostics, parallelization, and variance reduction techniques. Existing couplings of the Metropolis-Hastings algorithm handle the proposal and acceptance steps separately and fall short of the upper bound on one-step meeting probabilities given by the coupling inequality. This paper introduces maximal couplings which achieve this bound while retaining the practical advantages of current methods. We consider the properties of these couplings and examine their behavior on a selection of numerical examples.
more »
« less
- Award ID(s):
- 1844695
- PAR ID:
- 10225158
- Editor(s):
- Banerjee, Arindam; Fukumizu, Kenji
- Date Published:
- Journal Name:
- The 24th International Conference on Artificial Intelligence and Statistics
- Volume:
- 130
- Page Range / eLocation ID:
- 1225-1233
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider the double photoionization of the 2p2 valence electrons of atomic carbon, which provides for distinct final-state symmetries depending on the three possible angular momentum couplings (3P,1D, and 1S) of the initially-bound p2 electrons that are ejected into the continuum by a single photon. Comparison of this process with neon provides an analogous case for the resulting final states within the treatment of the double photoionization proceeding with the ejected electrons influenced by the remaining bound electrons.more » « less
-
null (Ed.)Abstract Semiconductor quantum-dot spin qubits are a promising platform for quantum computation, because they are scalable and possess long coherence times. In order to realize this full potential, however, high-fidelity information transfer mechanisms are required for quantum error correction and efficient algorithms. Here, we present evidence of adiabatic quantum-state transfer in a chain of semiconductor quantum-dot electron spins. By adiabatically modifying exchange couplings, we transfer single- and two-spin states between distant electrons in less than 127 ns. We also show that this method can be cascaded for spin-state transfer in long spin chains. Based on simulations, we estimate that the probability to correctly transfer single-spin eigenstates and two-spin singlet states can exceed 0.95 for the experimental parameters studied here. In the future, state and process tomography will be required to verify the transfer of arbitrary single qubit states with a fidelity exceeding the classical bound. Adiabatic quantum-state transfer is robust to noise and pulse-timing errors. This method will be useful for initialization, state distribution, and readout in large spin-qubit arrays for gate-based quantum computing. It also opens up the possibility of universal adiabatic quantum computing in semiconductor quantum-dot spin qubits.more » « less
-
A<sc>bstract</sc> The kinetic mixing of two U(1) gauge theories can result in a massless photon that has perturbative couplings to both electric and magnetic charges. This framework can be used to perturbatively calculate in a quantum field theory with both kinds of charge. Here we reexamine the running of the magnetic charge, where the calculations of Schwinger and Coleman sharply disagree. We calculate the running of both electric and magnetic couplings and show that the disagreement between Schwinger and Coleman is due to an incomplete summation of topological terms in the perturbation series. We present a momentum space prescription for calculating the loop corrections in which the topological terms can be systematically separated for resummation. Somewhat in the spirit of modern amplitude methods we avoid using a vector potential and use the field strength itself, thereby trading gauge redundancy for the geometric redundancy of Stokes surfaces. The resulting running of the couplings demonstrates that Dirac charge quantization is independent of renormalization scale, as Coleman predicted. As a simple application we also bound the parameter space of magnetically charged states through the experimental measurement of the running of electromagnetic coupling.more » « less
-
Differential privacy has emerged as a promising probabilistic formulation of privacy, generating intense interest within academia and industry. We present a push-button, automated technique for verifying ε-differential privacy of sophisticated randomized algorithms. We make several conceptual, algorithmic, and practical contributions: (i) Inspired by the recent advances on approximate couplings and randomness alignment, we present a new proof technique called coupling strategies, which casts differential privacy proofs as a winning strategy in a game where we have finite privacy resources to expend. (ii) To discover a winning strategy, we present a constraint-based formulation of the problem as a set of Horn modulo couplings (HMC) constraints, a novel combination of first-order Horn clauses and probabilistic constraints. (iii) We present a technique for solving HMC constraints by transforming probabilistic constraints into logical constraints with uninterpreted functions. (iv) Finally, we implement our technique in the FairSquare verifier and provide the first automated privacy proofs for a number of challenging algorithms from the differential privacy literature, including Report Noisy Max, the Exponential Mechanism, and the Sparse Vector Mechanism.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
