**nhaliday : fixed-point**
9

Is there a common method for detecting the convergence of the Gibbs sampler and the expectation-maximization algorithm? - Quora

october 2019 by nhaliday

In practice and theory it is much easier to diagnose convergence in EM (vanilla or variational) than in any MCMC algorithm (including Gibbs sampling).

https://www.quora.com/How-can-you-determine-if-your-Gibbs-sampler-has-converged

There is a special case when you can actually obtain the stationary distribution, and be sure that you did! If your markov chain consists of a discrete state space, then take the first time that a state repeats in your chain: if you randomly sample an element between the repeating states (but only including one of the endpoints) you will have a sample from your true distribution.

One can achieve this 'exact MCMC sampling' more generally by using the coupling from the past algorithm (Coupling from the past).

Otherwise, there is no rigorous statistical test for convergence. It may be possible to obtain a theoretical bound for the convergence rates: but these are quite difficult to obtain, and quite often too large to be of practical use. For example, even for the simple case of using the Metropolis algorithm for sampling from a two-dimensional uniform distribution, the best convergence rate upper bound achieved, by Persi Diaconis, was something with an astronomical constant factor like 10^300.

In fact, it is fair to say that for most high dimensional problems, we have really no idea whether Gibbs sampling ever comes close to converging, but the best we can do is use some simple diagnostics to detect the most obvious failures.

nibble
q-n-a
qra
acm
stats
probability
limits
convergence
distribution
sampling
markov
monte-carlo
ML-MAP-E
checking
equilibrium
stylized-facts
gelman
levers
mixing
empirical
plots
manifolds
multi
fixed-point
iteration-recursion
heuristic
expert-experience
theory-practice
project
https://www.quora.com/How-can-you-determine-if-your-Gibbs-sampler-has-converged

There is a special case when you can actually obtain the stationary distribution, and be sure that you did! If your markov chain consists of a discrete state space, then take the first time that a state repeats in your chain: if you randomly sample an element between the repeating states (but only including one of the endpoints) you will have a sample from your true distribution.

One can achieve this 'exact MCMC sampling' more generally by using the coupling from the past algorithm (Coupling from the past).

Otherwise, there is no rigorous statistical test for convergence. It may be possible to obtain a theoretical bound for the convergence rates: but these are quite difficult to obtain, and quite often too large to be of practical use. For example, even for the simple case of using the Metropolis algorithm for sampling from a two-dimensional uniform distribution, the best convergence rate upper bound achieved, by Persi Diaconis, was something with an astronomical constant factor like 10^300.

In fact, it is fair to say that for most high dimensional problems, we have really no idea whether Gibbs sampling ever comes close to converging, but the best we can do is use some simple diagnostics to detect the most obvious failures.

october 2019 by nhaliday

AlphaGo Zero: Minimal Policy Improvement, Expectation Propagation and other Connections

deepgoog acmtariat org:bleg nibble research summary papers liner-notes machine-learning deep-learning games auto-learning speedometer org:nat state-of-art ai reinforcement fixed-point detail-architecture

november 2017 by nhaliday

deepgoog acmtariat org:bleg nibble research summary papers liner-notes machine-learning deep-learning games auto-learning speedometer org:nat state-of-art ai reinforcement fixed-point detail-architecture

november 2017 by nhaliday

gn.general topology - Pair of curves joining opposite corners of a square must intersect---proof? - MathOverflow

october 2017 by nhaliday

In his 'Ordinary Differential Equations' (sec. 1.2) V.I. Arnold says "... every pair of curves in the square joining different pairs of opposite corners must intersect".

This is obvious geometrically but I was wondering how one could go about proving this rigorously. I have thought of a proof using Brouwer's Fixed Point Theorem which I describe below. I would greatly appreciate the group's comments on whether this proof is right and if a simpler proof is possible.

...

Since the full Jordan curve theorem is quite subtle, it might be worth pointing out that theorem in question reduces to the Jordan curve theorem for polygons, which is easier.

Suppose on the contrary that the curves A,BA,B joining opposite corners do not meet. Since A,BA,B are closed sets, their minimum distance apart is some ε>0ε>0. By compactness, each of A,BA,B can be partitioned into finitely many arcs, each of which lies in a disk of diameter <ε/3<ε/3. Then, by a homotopy inside each disk we can replace A,BA,B by polygonal paths A′,B′A′,B′ that join the opposite corners of the square and are still disjoint.

Also, we can replace A′,B′A′,B′ by simple polygonal paths A″,B″A″,B″ by omitting loops. Now we can close A″A″ to a polygon, and B″B″ goes from its "inside" to "outside" without meeting it, contrary to the Jordan curve theorem for polygons.

- John Stillwell

nibble
q-n-a
overflow
math
geometry
topology
tidbits
intricacy
intersection
proofs
gotchas
oly
mathtariat
fixed-point
math.AT
manifolds
intersection-connectedness
This is obvious geometrically but I was wondering how one could go about proving this rigorously. I have thought of a proof using Brouwer's Fixed Point Theorem which I describe below. I would greatly appreciate the group's comments on whether this proof is right and if a simpler proof is possible.

...

Since the full Jordan curve theorem is quite subtle, it might be worth pointing out that theorem in question reduces to the Jordan curve theorem for polygons, which is easier.

Suppose on the contrary that the curves A,BA,B joining opposite corners do not meet. Since A,BA,B are closed sets, their minimum distance apart is some ε>0ε>0. By compactness, each of A,BA,B can be partitioned into finitely many arcs, each of which lies in a disk of diameter <ε/3<ε/3. Then, by a homotopy inside each disk we can replace A,BA,B by polygonal paths A′,B′A′,B′ that join the opposite corners of the square and are still disjoint.

Also, we can replace A′,B′A′,B′ by simple polygonal paths A″,B″A″,B″ by omitting loops. Now we can close A″A″ to a polygon, and B″B″ goes from its "inside" to "outside" without meeting it, contrary to the Jordan curve theorem for polygons.

- John Stillwell

october 2017 by nhaliday

Controversial New Theory Suggests Life Wasn't a Fluke of Biology—It Was Physics | WIRED

august 2017 by nhaliday

First Support for a Physics Theory of Life: https://www.quantamagazine.org/first-support-for-a-physics-theory-of-life-20170726/

Take chemistry, add energy, get life. The first tests of Jeremy England’s provocative origin-of-life hypothesis are in, and they appear to show how order can arise from nothing.

news
org:mag
profile
popsci
bio
xenobio
deep-materialism
roots
eden
physics
interdisciplinary
applications
ideas
thermo
complex-systems
cybernetics
entropy-like
order-disorder
arrows
phys-energy
emergent
empirical
org:sci
org:inst
nibble
chemistry
fixed-point
wild-ideas
multi
Take chemistry, add energy, get life. The first tests of Jeremy England’s provocative origin-of-life hypothesis are in, and they appear to show how order can arise from nothing.

august 2017 by nhaliday

Lecture 6: Nash Equilibrum Existence

june 2017 by nhaliday

pf:

- For mixed strategy profile p ∈ Δ(A), let g_ij(p) = gain for player i to switch to pure strategy j.

- Define y: Δ(A) -> Δ(A) by y_ij(p) ∝ p_ij + g_ij(p) (normalizing constant = 1 + ∑_k g_ik(p)).

- Look at fixed point of y.

pdf
nibble
lecture-notes
exposition
acm
game-theory
proofs
math
topology
existence
fixed-point
simplex
equilibrium
ground-up
- For mixed strategy profile p ∈ Δ(A), let g_ij(p) = gain for player i to switch to pure strategy j.

- Define y: Δ(A) -> Δ(A) by y_ij(p) ∝ p_ij + g_ij(p) (normalizing constant = 1 + ∑_k g_ik(p)).

- Look at fixed point of y.

june 2017 by nhaliday

Complexity, ‘fog and moonlight’, prediction, and politics III – von Neumann and economics as a science – Dominic Cummings's Blog

albion wonkish polisci von-neumann economics social-science complex-systems comparison physics math science history quotes interdisciplinary fixed-point the-trenches stories giants behavioral-econ bounded-cognition early-modern humility s:* 🎩 thinking clarity empirical map-territory markets info-dynamics unaffiliated grokkability-clarity spock ratty

february 2017 by nhaliday

albion wonkish polisci von-neumann economics social-science complex-systems comparison physics math science history quotes interdisciplinary fixed-point the-trenches stories giants behavioral-econ bounded-cognition early-modern humility s:* 🎩 thinking clarity empirical map-territory markets info-dynamics unaffiliated grokkability-clarity spock ratty

february 2017 by nhaliday

Copy this bookmark: