text:
\begin{document}

\title{Quasi-stationary Random Overlap Structures and the continuous Cascades}
\author{Jason Miller}
\email{jmiller@math.stanford.edu}
\address{
\noindent Stanford University,
Department of Mathematics,
Building 380,
Stanford, CA 94305
}
\thanks{Research supported in part by NSF grants DMS-0406042 and DMS-0806211.}
\date{\today}
\maketitle

\begin{abstract}
A random overlap structure (ROSt) is a measure on pairs $(X,Q)$ where $X$ is a locally finite sequence in $\R$ with a maximum and $Q$ a symmetric positive semidefinite matrix of overlaps intrinsic to the particles $X$.  Such a measure is said to be quasi-stationary provided that the joint law of the gaps of $X$ and overlaps $Q$ is stable under a stochastic evolution driven by a Gaussian sequence with covariance $Q$.  Aizenman et al. show in \cite{AS203} that quasi-stationary ROSts serve as an important computational tool in the study of the Sherrington-Kirkpatrick (SK) spin-glass model from the perspective of cavity dynamics and the related ROSt variational principle for its free energy.  In this framework, the Parisi solution is reflected in the ansatz that the overlap matrix exhibit a certain hierarchical structure.  Aizenman et al. pose the question in \cite{AS207} of whether the ansatz could be explained by showing that the only ROSts that are quasi-stationary in a robust sense are given by a special class of hierarchical ROSts known as both the Ruelle Probability Cascades as well the GREM.  Arguin and Aizenman give an affirmative answer in \cite{AA07} and \cite{A_GG07} in the special case that the set of values $S_Q$ taken on by the entries of $Q$ is finite.  We prove that this result holds even when $|S_Q| = \infty$ provided that $Q$ satisfies the technical condition that $\overline{S_Q}$ has no limit points from below.  This is a relevant step towards understanding the ground states of the SK model, as they satisfy $|S_Q| = \infty$.
\end{abstract}

\section{Introduction}
A random overlap structure (ROSt) is a measure on pairs $(X,Q)$ where $X = (X_1 \geq X_2 \geq \cdots)$ is a locally finite sequence in $\R$ with a maximum and $Q = (q_{ij})$ a symmetric positive semidefinite $\N \times \N$ matrix of overlaps with $q_{ii} = 1$ for all $i$.  The overlaps are intrinsic to the particles $X$ and serve to quantify the degree to which they are related.  A ROSt is said to be quasi-stationary if the joint law of the gaps $(X_i - X_{i+1})$ and overlaps $Q$ is stable under the stochastic evolution
\begin{eqnarray}
\label{eqn::qs_not_norm}
X_i \mapsto X_{\pi(i)} + \psi(\kappa_{\pi(i)}),\ Q = (q_{ij}) \mapsto Q^\pi := (q_{\pi(i) \pi(j)}),
\end{eqnarray}
where conditional on $Q$, $(\kappa_i)$ is a Gaussian sequence with covariance $Q$ and $\pi$ is a permutation that restores the descending order of $X$.  Here, we assume $\psi \in \CC$ where $\CC$ is the set of all functions in $C^2(\R)$ with $\psi'(0) \neq 0$ that have the property $\E \exp(\lambda \psi(Z)) < \infty$ for all $\lambda \in \R$ and $Z$ a standard Gaussian.  Note that the evolution is defined so that the overlap of any two given particles is the same both before and after one step of the evolution.
From the cavity perspective of the Sherrington-Kirkpatrick (SK) model (see \cite{AS207}), it is natural to restrict our attention to those ROSts satisfying
\begin{equation}
\label{eqn::exponential_sum}
 \sum_i e^{\beta X_i} < \infty \text{ for some } \beta > 0.
\end{equation}
If we let $\xi$ be the normalized process $\xi_i = e^{\beta X_i}/\sum_j e^{\beta X_j}$ then the quasi-stationarity of (the law of) $(X,Q)$ translates into the stability of (the law of) $(\xi,Q)$ under the stochastic mapping
\begin{eqnarray}\label{eqn::qs}(\xi,Q) \mapsto \left( \left(\frac{ \xi_i e^{\psi(\kappa_i)}}{\sum_j \xi_j e^{\psi(\kappa_j)}} \right)_{\downarrow}, Q^\pi \right) ,\end{eqnarray}
where $\downarrow$ indicates a reordering and $\pi$ is again the order restoring permutation.  We break ties by saying that particles which have equal weight in the evolved structure are ordered according to their position in the original structure.  In the case that $\xi_i \equiv 0$ for all $i$, we take the evolved weights also to be identically zero.  Let $d_{ij} = \delta_{ij} -q_{ij}$.  We say that $Q$ is ultrametric if $d_{ij} \leq \max(d_{ik},d_{kj})$ for all $i,j,k$.  Note that ultrametricity implies that the relation $i \sim_q j$ if and only if $q_{ij} \geq q$ is an equivalence.

Motivated by the cavity picture and the Parisi ansatz (see \cite{PA80}, \cite{TAL03}, \cite{TAL06}) for the SK model it is of considerable interest to characterize those structures that are quasi-stationary and to understand the relationship between quasi-stationarity and the ultrametricity of the overlap matrix.  The first step in this direction was taken by Ruzmaikina and Aizenman in \cite{RA05} where they show that, in the special case $Q$ is the identity matrix so that the Gaussian sequence $(\kappa_i)$ is iid, the quasi-stationary laws (without the normalization) are given by mixtures of Poisson processes with exponential intensities, i.e. of the form $ye^{-ys} ds$ with $y > 0$.  The Ruzmaikina-Aizenman theorem holds under the technical condition that there exists constants $A, r > 0$ such that
\begin{equation}
\label{eqn::expected_bound}
\E|\{ n : X_1 - X_n \leq d\}| \leq A e^{rd},
\end{equation}
where $|\cdot|$ denotes the cardinality of a set.  Recall that $\xi$ is said to follow the Poisson-Dirichlet distribution with parameter $x \in (0,1)$, denoted by $\xi \sim PD(x,0)$, if $(\xi_i) \stackrel{d}{=} (X_i / \sum_j X_j)$, where $X = (X_1 \geq X_2 \geq \cdots \geq 0)$ is a Poisson process with intensity $xs^{-x-1}ds$.  Note that densities of the latter form arise from the former via an exponential change of variables.
In \cite{A07}, Arguin shows that the Ruzmaikina-Aizenman theorem is also true when the hypothesis \eqref{eqn::expected_bound} is replaced by \eqref{eqn::exponential_sum} which implies that the normalized quasi-stationary ROSts $(\xi,Q)$ with $Q$ the identity matrix are exhausted by the mixtures of $PD(x,0)$ variables.  In this article we restrict our attention to quasi-stationarity in the normalized case.

For $r \in \N$, let $Q^{*r} = (q_{ij}^r)$ denote the $r$th Schur power of $Q$, i.e. entrywise product of $Q$ with itself $r$ times.  If $Q$ is symmetric and positive semidefinite then $Q^{*r}$ is as well \cite{HJ85}.  Fix $\psi \in \CC$ and for $r \in \N$, $\lambda \in \R$, let $\Phi_{r,\lambda}$ be the stochastic map,
\[ \Phi_{r,\lambda}(\xi,Q) := \left(\left( \frac{\xi_i e^{\lambda \psi(\kappa_i)}}{\sum_j \xi_j e^{\lambda \psi(\kappa_j)}} \right)_\downarrow, Q^\pi \right),\]
 where the Gaussian sequence $(\kappa_i)$ is generated with covariance $Q^{*r}$.  We say that a ROSt is $(r,\lambda)$-quasi-stationary for $\psi$ if its law is stable $\Phi_{r,\lambda}$.  A ROSt is said to be robustly quasi-stationary (RQS) provided that it is $(r,\lambda)$-quasi-stationary for all $r \in \N$ and $\lambda > 0$.  Let $S_Q = \{q_{ij} : i,j \in \N, i \neq j\}$ denote the state space of $Q$ and $S_Q(i) = \{q_{ij} : j \neq i, j \in \N\}$.  The overlap matrix $Q$ is said to be indecomposable provided that $S_Q(i) = S_Q$ for every $i$; this condition represents a sort of self-similarity of the particles which is natural in the context of the SK model.  In \cite{AA07}, Arguin and Aizenman show that if $(\xi,Q)$ is RQS, ergodic for the correlated evolution with $S_Q \subseteq (-1,1)$, $|S_Q| < \infty$, and $Q$ indecomposable then $(\xi,Q)$ is given by a finite level Ruelle Probability Cascade (RPC), a special type of ROSt with ultrametric overlaps arising from a hierarchy of Poisson processes which we describe in the next section.  In the case that $Q$ is not indecomposable, there is a natural equivalence between particles where $\xi_i \sim \xi_j$ if and only if $S_Q(i) = S_Q(j)$.  As the set $S_Q(i)$ is intrinsic to $\xi_i$, this equivalence is invariant under the evolution so that the equivalence classes are themselves RQS, ergodic, and indecomposable and hence given by RPCs \cite{AA07}.  In \cite{A_GG07}, Arguin shows that the assumption of indecomposability can be removed by arguing that the equivalence classes have the same state space and hence must be equal.  By convexity, the results of \cite{AA07} and \cite{A_GG07} imply that the set of RQS ROSts with finite state space are given by superpositions of finite level RPCs.  Our main theorem is that this result holds even if $|S_Q| = \infty$ provided that $S_Q$ satisfies the technical condition that $\overline{S_Q}$ does not have limit points from below:
\begin{theorem}
\label{thm::main_theorem}
If $(\xi,Q)$ is a robustly quasi-stationary random overlap structure with $S_Q \subseteq (-1,1)$ and ergodic for the evolution \eqref{eqn::qs} such that if $q \in \overline{S_Q}$ then $\sup\{ p \in \overline{S_Q}, p < q\} < q$, then $(\xi,Q)$ is given by a continuous Ruelle Probability Cascade.  In particular, all such laws are ultrametric and satisfy $S_Q \subseteq [0,1)$.
\end{theorem}
\noindent The condition of robustness is necessary to single out the cascades.  At the end of the next section, we will show that for each fixed $R \in \N$ there exists a ROSt that is $(r,\lambda)$-quasi-stationary with respect to $\psi(x) = x$ for all $\lambda > 0$ and all $r \leq R$ that is not an RPC.  The relaxation of the restriction that $S_Q$ is finite is a relevant step towards the understanding of the ground states of the SK model as in this case $|S_Q| = \infty$.  Note that the assumption that $\overline{S_Q}$ does not have limit points from below allows for $S_Q$ to be rather complicated.  For example, the number of cluster points of $S_Q$ could be infinite.

The proof in \cite{AA07} is by induction on $|S_Q|$ and has the following structure.  First, assume that $\psi(x) = \lambda x$ is linear.  Taking a limit as $r \to \infty$ the non-diagonal entries of $Q^{*r}$ tend to zero from which it follows that RQS implies quasi-stationarity under the free evolution, the evolution driven by an iid Gaussian sequence $(\kappa_i)$.  The latter gives that $\xi$ is independent of $Q$ and, by \cite{A07}, $\xi$ follows a $PD(x,0)$ distribution.  By looking at the past increments, it can be deduced that $Q$ is weakly exchangeable.  Hence by a version of de Finetti's theorem for weakly exchangeable covariance matrices proved in \cite{DS82}, there exists a random measure $\nu$ on a separable Hilbert space $\CH$ so that conditional on $\nu$ the distribution of $Q=(q_{ij})$ is given by $q_{ij} \stackrel{d}{=} (\phi_i,\phi_j) + \delta_{ij} (1-\|\phi_i\|^2)$ where $(\phi_i)$ is a $\nu$-iid sequence; we refer to $\nu$ as the \emph{directing measure} of $(\xi,Q)$.   That $S_Q$ is finite and indecomposable is used to conclude that $\nu$ admits the representation $\nu = \sum_j \eta_j \delta_{\psi_j}$ where $\| \psi_j\|^2 = \sup S_Q < 1$ is constant for all $j$.  Viewing $(\xi,Q)$ as a marked Poisson-Dirichlet process with marking measure $\nu$, RQS implies that the ROSt $(\eta,P)$, $P =(p_{ij})$, $p_{ij} = (\psi_i,\psi_j)/\sup S_Q$ is itself RQS but with $|S_P| = |S_Q|-1$.  The induction step follows as $(\xi,Q)$ can be reconstructed from $(\eta,P)$ in exactly the same way that a $k$-level RPC can be constructed from a $k-1$ level RPC (see Proposition \ref{prop::rpc_construction}).  The case that $\psi$ is non-linear can be reduced to the linear case via an argument with the central limit theorem.

A new proof is required in the infinite case for two reasons.  First, the argument that the directing measure is countably supported on a non-random sphere crucially depends on the indecomposability of $Q$.  It turns out that this holds more generally, but requires a different argument.  Second, the induction fails in the infinite case due to the possibility of many cluster points in $S_Q$.  Our approach is as follows. We use a continuity argument in Section \ref{sec::closure} to show that the closure of the set of finite level RPCs is the set of continuous RPCs provided we equip the space of ROSts with an appropriate topology.  Next, we show in Section \ref{sec::approx} that ergodic RQS ROSts with state space that has no limit points from below can be approximated arbitrarily well by such ROSts with indecomposable finite state space.  This step is non-trivial since it requires constructing an approximation that remains a fixed point of an infinite collection of maps.

\section{Ruelle Probability Cascades}

In this section we recall the construction of the finite level RPCs given by Ruelle in \cite{RU87}, following closely that given in \cite{AA07}.  Fix $k \in \N$ and $2k$ parameters
\[ 0 = q_0 \leq q_1 < q_2 < \cdots <  q_{k+1} =1,\]
and
\[ 0 = x_0 <  x_1 < x_2 < \cdots < x_{k+1} = 1.\]
Define a right-continuous function on $[0,1]$,
\[ x(q) =  \sum_{l=0}^k x_l 1_{[q_l,q_{l+1})}(q)\]
and let $q(x)$ be the right continuous inverse of $x(q)$:
\[ q(x) = \inf\{ t : x(t) > x\} = \sum_{l=1}^{k+1} q_l 1_{[x_{l-1},x_l)}(x).\]
One often specifies $x(q)$ as the order parameter of an RPC, but for us it will be more convenient to work with $q(x)$.  This perspective is without loss of generality as the association of $x(q)$ with $q(x)$ is injective.  Let $\alpha = (\alpha_1,\ldots,\alpha_k) \in \N^k$.  Denote by $\alpha(l) = (\alpha_1,\ldots,\alpha_l)$ the truncation of $\alpha$ up to its $l$th component; set $\alpha(0) = 0$.  For each $\alpha(l)$, $0 \leq l \leq k-1$, let $\eta^{\alpha(l)}$ be an independent Poisson process with intensity $x_{l+1} s^{-x_{l+1}-1} ds$.  We denote by $\eta_j^{\alpha(l)}$ the $j$th largest element of $\eta^{\alpha(l)}$.  Now define the point process,
\[ \eta = (\eta_\alpha : \alpha \in \N^k) = (\eta_{\alpha_1}^0 \eta_{\alpha_2}^{\alpha(1)} \cdots \eta_{\alpha_k}^{\alpha(k-1)} : \alpha \in \N^k).\]
As each $\eta^{\alpha(l)}$ is summable it follows that $\eta$ is summable and can be ordered.  Let
\[ N = \sum_{\alpha} \eta_\alpha \text{ and } \xi = \left( \frac{1}{N} \eta_\alpha \right)_{\downarrow}\]
be the normalization of the ordering of $\eta$ to have unit sum.  Fix $i,j$.  Then $\xi_i = N^{-1} \eta_\alpha$ and $\xi_j = N^{-1} \eta_\beta$ for some $\alpha,\beta \in \N^k$.  Let $\sim_l$ be the equivalence relation on $\N$ given by $i \sim_l j$ if and only if the truncations $\alpha(l)$ and $\beta(l)$ agree.  Let $l(i,j)$ be the largest $l$ such that $i \sim_l j$, set
\[q_{ij} = q_{l(i,j)+1} = q(x_{l(i,j)}),\]
and let $Q = (q_{ij})$.  Then $(\xi,Q)$ defines a ROSt, which we refer to as a $k$-level RPC; we will also refer to $(\xi,Q)$ as a finite level RPC if we do not wish to specify the number of levels.  We can think of the association of the parameter $q(x)$ with $(\xi,Q)$ given by the RPC with order parameter $q(x)$ as a map from the set of finite valued non-decreasing right-continuous step functions on $[0,1]$ into the space of ROSts.  In the sequel we will prove that if we equip these spaces with appropriate (and natural) topologies, this map is a homeomorphism when the parameter $x_k$ is fixed but the number of levels $k$ is allowed to vary.

Let
\[u_1 = \log\left(\frac{x_k}{x_1}\right), u_2 = \log\left( \frac{x_k}{x_2}\right),\ldots,u_k = \log\left(\frac{x_k}{x_k}\right) = 0\]
and denote by $\Gamma_{u_j}$ the equivalence classes of $\sim_j$ in $\N$.  Then we can think of $(\Gamma_{u_j} : j=k,\ldots,1)$ as a process on $\CE(\N)$, the set of equivalence relations on $\N$.  It turns out that $(\Gamma_{u_j})$ is the discrete skeleton of a continuous time Markov process  $(\Gamma_u : u \geq 0)$ with initial distribution the equivalence given by equality and semigroup $R_u(\Gamma,d\Gamma')$, $u \geq 0$, given as follows (Proposition 1.1, Theorem 1.2, Theorem 2.2 \cite{BS98}).  When $u = 0$, $R_u(\Gamma,d\Gamma')$ is the $\delta$ mass supported at $\Gamma$.  When $u > 0$, construct a random variable $\Gamma' $ taking values in $\CE(\N)$ by first generating a $PD(x,0)$ variable $\eta$ with $x = e^{-u}$, then picking $\eta$ (thought of as a probability on $\N$) iid random integers $y_C$ indexed by $C \in \Gamma$, and letting $\Gamma'$ be the set of equivalence classes,
\[ C_j' = \bigcup_{y_C = j} C.\]
Then $R_u(\Gamma,d\Gamma')$ is the law of $\Gamma'$.  The process $(\Gamma_u)$ is called the Bolthausen-Sznitman coalescent and can be used to give a concrete specification of Ruelle's direct limit construction of the continuous RPCs.  If $q \colon [0,1] \to [0,1]$ is a non-decreasing right-continuous function such that $q(\zeta) = 1$ for $\zeta \in (0,1)$ we associate with $(\Gamma_u)$ a ROSt $(\xi,Q)$ where $\xi \sim PD(\zeta,0)$ is independent of $(\Gamma_u)$ and $Q = (q_{ij})$ where $q_{ij} = q(\tau_{ij})$,
\[  \tau_{ij} =  \inf\{ u > 0 : i,j \text{ are in the same } \Gamma_u \text{ equivalence class}\}.\]
We refer to $(\xi,Q)$ as a continuous RPC with parameters $q,\zeta$.  In the special case that $q$ is a step function with $\zeta = \inf\{ x : q(x) = 1\}$ then $(\xi,Q)$ has the law of the finite level RPC parameterized by $q$.

An immediate consequence of this is the following alternative construction of the finite level RPCs originally due to Bolthausen and Sznitman in \cite{BS98}, through reformulated as follows as Theorem 2.5 of \cite{AA07}.
\begin{proposition}
\label{prop::rpc_construction}
The distribution of the RPC $(\xi,Q)$ with parameters $0 = q_0 \leq q_1 < \cdots  < q_k <  q_{k+1} = 1$, $0 = x_0 <  x_1 < \cdots < x_k < x_{k+1} = 1$ satisfies the following:
\begin{enumerate}
 \item $\xi$ and $Q$ are independent,
 \item $\xi \sim PD(x_k,0)$, and
 \item Suppose that $(\xi',Q') = (q_{ij}')$ is independent of $\xi$ and distributed as a $k-1$ level RPC with parameters $q_1/q_k < \cdots < q_{k-1}/q_k$ and $x_1/x_k < \cdots < x_{k-1}/x_k$.  Then, conditional on $(\xi',Q')$, $Q \stackrel{d}{=} (q_{ij})$ where $q_{ij} = q_k q_{i^* j^*}'$ with $i^*$ denoting the $i$th element of a sequence $(i^*)$ of $\xi'$ (thought of as a probability on $\N$) iid random integers.
\end{enumerate}
\end{proposition}

Proposition \ref{prop::rpc_construction} is used in the proof of Theorem 2.9 of \cite{AA07} to show that the finite level RPCs are RQS.  We will sketch the argument in the case that $\psi(x) = \lambda x$ is linear, the general case being roughly the same but with more complicated notation.  First, note that if $(\xi,Q)$ is a $k$-level RPC with order parameter $q(x)$ then $(\xi,Q^{*r})$ is also a $k$-level RPC but with order parameter $q^r(x)$.  Hence that $(\xi,Q)$ is RQS will follow if we can show that $(\xi,Q)$ is quasi-stationary for the correlated evolution.  When $k=1$ we can decompose the Gaussian increments as $\kappa_i = \kappa^c + \kappa_i^f$ where $\kappa^c$ is the common shift and $(\kappa_i^f)$ is an iid sequence of Gaussian random variables with variance $(1-q_1^2)$.  The common part $\kappa^c$ gets canceled in the normalization \eqref{eqn::qs} and hence in this case the correlated evolution is the same as the free evolution.  As $\xi \sim PD(x_1,0)$, the law of $\xi$ is invariant; $Q$ is trivially invariant as its non-diagonal entries are constant.  Now suppose $(\xi,Q)$ is a $k \geq 2$ level cascade and let $(\xi',Q')$ be a $k-1$ level cascade as in Proposition \ref{prop::rpc_construction}.  Conditional on $(\xi',Q')$, $(\xi,Q)$ can be viewed as a marked Poisson-Dirichlet variable with the mark of $\xi_i$ being its ``parent'' in $(\xi',Q')$.  The Gaussian sequence of increments $(\kappa_i)$ can again be decomposed as $\kappa_i = \kappa_i^c + \kappa_i^f$ where $\kappa_i^f$ are iid with variance $(1-q_{k}^2)$.  Conditional on the realization of $\kappa_i^c$, the evolution is that of a marked $PD(x_k,0)$ variable with mark dependent increments.  One can show using the probability mass generating functional (Lemma 2.7 of \cite{AA07}, see also Proposition A.2 of \cite{BS98}) that the resulting process is again a marked $PD(x_k,0)$ variable but with a new marking measure.  It turns out that in this case the evolution of the marking measure exactly corresponds to the correlated evolution of the $k-1$ level cascade $(\xi',Q')$, which we know by induction to be quasi-stationary.  As the set of RQS laws is closed (Proposition \ref{prop::rqs_closed}), it follows from the continuity argument given in the next section that the continuous RPCs are also RQS.

We will now show that the hypothesis of robustness is necessary to single out the cascades using a construction due to Arguin \cite{A08}.  Suppose that $(\xi,Q)$ is a finite level cascade with parameter $q(x)$ and $\xi \sim PD(\zeta,0)$, $\zeta \in (0,1)$.  The proof of Theorem 2.9 of \cite{AA07} implies that if $q_1 = 0$ then for each $r \in \N$ and $\lambda > 0$ there exists a deterministic quantity $v(r,\lambda)$ such that
\[ \left( \left( \xi_n e^{\lambda \kappa_n} \right)_\downarrow, Q^\pi\right) \stackrel{d}{=} \big( (e^{v(r,\lambda)} \xi_n), Q \big),\]
where the $(\kappa_n)$ are Gaussian with covariance $Q^{*r}$; $v(r,\lambda)$ is referred to as the $(r,\lambda)$-crowd velocity of $(\xi,Q)$.  In other words, the renormalization constant in \eqref{eqn::qs} is a deterministic function of $r$, $\lambda$, and the parameters of the RPC.  In fact, one can compute $v(r,\lambda)$ explicitly (Theorem 5.4, \cite{AS207}),
\[ v(r,\lambda) = \frac{\lambda^2}{2} \int_0^1 (1-q^r) dx(q).\]
This implies that if $(\xi^1,Q^1)$ and $(\xi^2,Q^2)$ are independent RPCs with equal $(r,1)$-crowd velocity, the ROSt $(\xi,Q)$ constructed by taking the union of the particles in $\xi^1,\xi^2$ with overlaps between particles of $\xi^i$ given by $Q^i$ and between $\xi^1,\xi^2$ given by $0$ is $(r,\lambda)$-quasi-stationary for all $\lambda > 0$.  Such ROSts are easily seen not to be RPCs in general.  Furthermore, fixing $R \in \N$ and then choosing distinct RPCs $(\xi^1,Q^1),(\xi^2,Q^2)$ so that they have the same $(r,1)$-velocity for all $r \leq R$ one can construct examples of ROSts that are $(r,\lambda)$-quasi-stationary for all $r \leq R$ and $\lambda > 0$ that are not RPCs.  This technique can be extended to build much more elaborate examples of quasi-stationary ROSts using a variation of Proposition \ref{prop::rpc_construction} and RPCs as the basic building blocks.  Nevertheless, such ROSts still have ultrametric overlaps and it remains an important question to determine if quasi-stationarity alone implies ultrametricity.

\section{Preliminaries}
\label{sec::closure}

The goal of this section is to prove that the set of RQS ROSts is closed and that the closure of the set of finite level RPCs is given by the set of continuous RPCs.  In order to do this, we need to specify a topology (same as is used in \cite{AA07}). Let $P_m$ be the set of mass partitions $\{\xi_1 \geq \xi_2 \geq \cdots \geq 0 : \sum_{i=1}^\infty \xi_i \leq 1\}$ and $\CQ$ the set of symmetric positive semidefinite $\N \times \N$ matrices $Q = (q_{ij})$ with $q_{ii} = 1$ for all $i$.  We equip $P_m$ with the metric induced by the $\ell^\infty$ norm and $\CQ$ with the product topology.  The latter can be metrized with the distance,
\[ d(Q,P) = \sum_{i,j=1}^\infty 2^{-i-j} |q_{ij} - p_{ij}|.\]
Note that both of these topologies are compact.  Denote by $\Omega_{os} = P_m \times \CQ$ the set of overlap structures and $\CM_1(\Omega_{os})$ the set of ROSts, i.e. the Borel regular probability measures on $\Omega_{os}$.  We equip $\CM_1(\Omega_{os})$ with the weak topology.  Observe that $\Phi_r = \Phi_{r,1}$ is \emph{not} continuous with respect to this topology.  For example, if one considers the sequence of ROSts $(\xi^n,Q^n)$ where $\xi^n$ consists of a single particle at $\frac{1}{n}$ and $Q^n$ is the identity matrix then $(\xi^n,Q^n) \to (\xi,Q)$ which is the ROSt where all of the particles have zero mass while for all $n$, $\Phi_r(\xi^n,Q^n)$ consists of a single particle at $1$.  Nevertheless, the set of RQS ROSts is closed in the $\Omega_{os}$ topology.  We remark that if one changes the topology of $P_m$ to that induced by the $\ell^1$ norm then $\Phi_r$ is in fact continuous but this topology is not compact so that we do not have the desired ergodic decomposition.

\begin{proposition}
\label{prop::rqs_closed}
The set of RQS laws is closed in $\CM_1(\Omega_{os})$.
\end{proposition}
\begin{proof}
Observe that $(\xi,Q) \mapsto \Phi_r(\xi,Q)$ is weakly continuous in $Q$.  Suppose that $(\xi^n,Q^n)$ is a sequence of RQS ROSts converging in the topology of $\CM_1(\Omega_{os})$ to $(\xi,Q)$.  By Theorem 1.9 of \cite{AA07} we know that for each $n$ there exists a parameter $X_n \in (0,1)$ measurable with respect to $\sigma(\xi^n)$ such that conditional on $X_n$, $\xi^n \sim PD(X_n,0)$.  By passing to a subsequence we may assume without loss of generality that $X_n$ converges weakly to $X \in [0,1]$.  A simple computation with the mass generating functional shows that conditional on $X$, $\xi \sim PD(X,0)$.  Furthermore, as $\xi^n$ is independent of $Q^n$ for all $n$ it follows that $\xi$ is independent of $Q$.  Proposition \ref{prop::rescale_direct} implies that if $(\eta,P)$ is RQS and $\xi$ is a mixture of Poisson-Dirichlet distributions independent of $P$ then $(\xi,P)$ is RQS.  We can embed $(\xi^n,Q^n)$ and $(\xi,Q)$ into a common probability space such that $\xi$ is independent of $Q^n$ for all $n$ so that in particular $(\xi,Q^n)$ is RQS.  Combining everything,
\begin{align*}
   (\xi,Q) \stackrel{d}{=} \lim_n (\xi,Q^n) \stackrel{d}{=} \lim_n \Phi_r(\xi,Q^n) \stackrel{d}{=} \Phi_r(\xi, \lim_n Q^n),
\end{align*}
from which the proposition follows.
\end{proof}

Fix $\zeta \in (0,1)$ and let $\overline{X} = \overline{X}(\zeta)$ be the set of functions $q$ on $[0,1]$ that are right-continuous, non-decreasing, and $q(x) = 1$ for all $x \geq \zeta$.  Let $X$ be the set of $q \in \overline{X}$ with finite range.  Equip $\overline{X}$ with the topology induced by the $L^1([0,1])$ norm; observe that the closure of $X$ is $\overline{X}$.  The association of the parameter $q \in X$,
\[ q(x) = \sum_{l=1}^{k+1} q_l 1_{[x_{l-1},x_l)},\ x_k = \zeta,\]
with a finite level RPC induces a map $T \colon X \to \CM_1(\Omega_{os})$ that is trivially invertible.  Let $Y = Y(\zeta) = T(X)$ be the set of finite level RPCs $(\xi,Q)$ in $\CM_1(\Omega_{os})$ with $\xi \sim PD(\zeta,0)$.  Denote by $\overline{Y}$ its closure.
\begin{proposition}
\label{prop::rpc_homeo}
The map $T$ is uniformly continuous with uniformly continuous inverse.  In particular, $T$ extends uniquely to a homeomorphism $\overline{T} \colon \overline{X} \to \overline{Y}$.
\end{proposition}

It is not hard to see that for $q \in \overline{X}$, $\overline{T}(q)$ is the same as the ROSt induced by the Bolthausen-Sznitman coalescent with overlap parameter $q$.  The most important consequence of Proposition \ref{prop::rpc_homeo} for us is that $\overline{Y}$ consists precisely of the continuous RPCs with Poisson-Dirichlet parameter $\zeta$.  Suppose that $(\xi,Q)$ is a finite level RPC.  We say that particles $\xi_i,\xi_j$ overlap at level $r$ provided that $l(i,j) = r$, $l(i,j)$ as defined in the previous section.  The proof of Proposition \ref{prop::rpc_homeo} depends on the following estimate that any of the largest $n$ particles overlap at a particular level.

\begin{lemma}
\label{lem::overlap_prob}
Let $q \in X$, $(\xi,Q)$ be an RPC with parameter $q$, and $0 = x_0 < x_1 < \cdots < x_{k} = \zeta < x_{k+1} = 1$ be the endpoints of the intervals on which $q$ is constant.  Let
\[ A_n^r = \bigcup_{1 \leq i < j \leq n} \{\xi_i,\xi_j \text{ overlap at level } r\}.\]
Then,
\[ |x_{r+1} - x_r| \leq \p(A_n^r) \leq C(n,\zeta)|x_{r+1} - x_r|,\]
where $C(n,\zeta) = \tfrac{1}{2\zeta}n(n-1)$.
\end{lemma}
\begin{proof}
Applying Proposition \ref{prop::rpc_construction} inductively, there exists independent processes $\eta^1,\ldots,\eta^{k-1}$ such that $\eta^l \sim PD(x_l/x_{l+1},0)$ for $1 \leq l \leq k-1$ and
\[ Z = \p(A_2^r|\eta^1,\ldots, \eta^{k-1}) = \left( \prod_{l=r+1}^{k-1} \sum_{m=1}^\infty \eta_m^l(1-\eta_m^l) \right) \sum_{m=1}^\infty (\eta_m^r)^2\]
is the probability that $\xi_1,\xi_2$ overlap at level at $r$ conditional on $\eta^1,\ldots,\eta^{k-1}$.  For $n \geq 2$, observe
\[ Z \leq \p(A_n^r|\eta^1,\ldots,\eta^{k-1}) \leq \frac{n(n-1)}{2} Z.\]
If $\gamma \sim PD(x,0)$ and $n \geq 2$ then (Proposition A.1 of \cite{BS98}, Corollary 2.2(a) of \cite{RU87}),
\[ \E \sum_{m=1}^\infty \gamma_m^n = \frac{(n-1-x)(n-2-x) \cdots (1-x)}{(n-1)!}.\]
Hence if $1 \leq r \leq k-1$,
\begin{align*}
     \E Z
&= \E \left( \prod_{l=r+1}^{k-1} \sum_{m=1}^\infty \eta_m^l (1-\eta_m^l) \right) \sum_{m=1}^\infty (\eta_m^r)^2
  = \left(\prod_{l=r+1}^{k-1}  \left( 1- \E \sum_{m=1}^\infty (\eta_m^l)^2 \right) \right) \E \sum_{m=1}^\infty (\eta_m^r)^2\\
&= \left(\prod_{l=r+1}^{k-1} \frac{x_l}{x_{l+1}} \right) \left(1 - \frac{x_r}{x_{r+1}} \right)
  = \frac{1}{\zeta} (x_{r+1} - x_r).
\end{align*}
Similarly, if $r = 0$,
\begin{align*}
     \E Z
&= \left(\prod_{l=1}^{k-1} \frac{x_l}{x_{l+1}} \right)
 = \frac{1}{\zeta} (x_{1} - x_0).
\end{align*}
\end{proof}

\begin{proof}[Proof of Proposition \ref{prop::rpc_homeo}]
Let $\epsilon > 0$ be arbitrary and suppose $f,g \in X$ are such that $\| f - g\|_{L^1} \leq \epsilon^2$.  Let $(\xi,Q)$ and $(\eta,P)$ be random variables with the laws of $T(f)$ and $T(g)$.  We assume that $(\xi,Q)$ and $(\eta,P)$ are constructed by taking $\xi = \eta$ and $Q$ and $P$ generated from the same Bolthausen-Sznitman coalescent.  Hence the distance between $(\xi,Q)$ and $(\eta,P)$ is completely determined by $d(Q,P)$.  Take $n = [-\log_2 \epsilon ] + 1$ so that $\sum_{i \vee j \geq n+1} 2^{-i-j} \leq \epsilon$.  Then,
\[ d(Q,P) = \sum_{i,j=1}^\infty 2^{-i-j} |q_{ij} - p_{ij}| \leq \max_{1 \leq i,j \leq n} |q_{ij} - p_{ij}| + \epsilon.\]
Let $I_1 = [x_{i_1},x_{i_1+1}), \ldots, I_m = [x_{i_m},x_{i_m+1})$ be the disjoint intervals such that $E = \{|f-g| \geq \epsilon\} = \cup_{j=1}^m I_j$.  Using the notation of Lemma \ref{lem::overlap_prob},
\begin{align*}
     \p(\max_{1 \leq i,j \leq n} |q_{ij} - p_{ij}| \geq \epsilon)
&= \p(A_n^{i_1} \cup \cdots \cup A_n^{i_m})
 \leq C(n,\zeta) \sum_{j=1}^m |x_{i_j} - x_{i_j+1}|\\
&= \frac{n(n-1)}{2\zeta} |E|
  \leq \frac{n(n-1)}{2\zeta} \epsilon.
\end{align*}
Therefore,
\[ \p(d(Q,P) \geq 2\epsilon) \leq \frac{n(n-1)}{2\zeta} \epsilon.\]
The quantity on the right hand side clearly goes to zero as $\epsilon \to 0$.  This proves that $T$ is uniformly continuous.

Now assume $\p(d(Q,P) \geq \epsilon^2) \leq \epsilon$.  With $n = [-\tfrac{1}{2} \log_2 \epsilon]$, note
\[ d(Q,P) \geq 2^{-2n} \max_{1 \leq i,j \leq n} |q_{ij} - p_{ij}| \geq \epsilon \max_{1 \leq i,j \leq n} |q_{ij} - p_{ij}|.\]
Let $E$ and $I_{1},\ldots,I_m$ be as before.  As the collection $A_2^{i_1},\ldots,A_2^{i_m}$ is disjoint,
\[ \p(\max_{1 \leq i,j \leq n} |q_{ij} - p_{ij}| \geq \epsilon) = \p(A_n^{i_1} \cup \cdots \cup A_n^{i_m}) \geq \p(A_2^{i_1} \cup \cdots \cup A_2^{i_m}) = |E|.\]
Trivially, we have the bound,
\[ \| f -g \|_{L^1} \leq \epsilon + |E| \leq 2\epsilon.\]
Therefore $T^{-1}$ is uniformly continuous.
\end{proof}

\section{Approximation}
\label{sec::approx}

In this section we will show that every ROSt which is RQS for $\psi$ linear and non-constant, ergodic for the evolution, with $S_Q \subseteq (-1,1)$ (RQSE) can be approximated arbitrarily well by an RQSE ROSt with finite state space provided that $\overline{S_Q}$ has no limit points from below.  This means that if $q \in \overline{S_Q}$, $\sup\{ p \in \overline{S_Q} : p < q\} < q$.  The proof of Theorem 1.8 of \cite{AA07} implies that the restriction to $\psi(x) = x$ linear is without loss of generality.  Our strategy is to prove that if $g \colon [-1,1] \to [-1,1]$ is any non-decreasing right continuous step function with $g(x) \leq x$ for all $x \in [-1,1]$ and fixing $-1$, $0$, and $1$ then $(\xi,g(Q))$, here and hereafter $g(Q) = (g(q_{ij}))$ denotes entrywise application of $g$, is RQSE.  Establishing this fact consists of three main steps.  First, we will show that $S_Q$ has an $n$th largest element for every $n \leq |S_Q|$ that will necessarily be non-negative.  Second, by a scaling argument we can alter the first $n \leq |S_Q|$ elements of $S_Q$ maintaining positive-definiteness and RQSE so long as the order is preserved.  Third, it is possible to take a kind of limit that allows us to alter the entire state space.

Recall that a random measure $\nu$ on $\CH$, $\CH$ a separable Hilbert space, is said to direct $(\xi,Q)$ provided that conditional on $\nu$, $q_{ij} \stackrel{d}{=} (\phi_i,\phi_j) + \delta_{ij} (1-\|\phi_i\|^2)$ where $(\phi_i)$ is a $\nu$-iid sequence.  It is a consequence of Theorems 1.9 and 1.10 of \cite{AA07} that every RQSE ROSt is directed.  In the following two lemmas we show that the directing measure of such a ROSt is supported in a non-random sphere and that if $\overline{S_Q}$ does not have limit points from below, $\nu$ has countable support.

It is shown in \cite{A_GG07} that for each RQSE ROSt $(\xi,Q)$ and fixed $r, \lambda > 0$ there exists an extension of the probability measure
\[ d\p_{r,\lambda} = d\p(\xi,Q) \times \prod_{t \geq 0} d \nu_{Q^{*r}}(\kappa(t)),\]
which is the law of $(\xi,Q)$ and its future increments under the $Q^{*r}$ evolution with $\psi(x) = \lambda x$, to $\Omega_{os} \times \prod_{t \in \Z} \R^\N$; the negative indices correspond to the past increments.  The construction follows by showing that the map $\Lambda \colon \Omega_{os} \times \prod_{t \geq -n} \R^\N \to \Omega_{os} \times \prod_{t \geq -n-1} \R^\N$ given by evolving $(\xi,Q)$ by the Gaussian sequence $(\kappa_i(0))$, reordering, and then shifting the index of the increments by $-1$ induces a consistent family of measures.  We abuse notation and write $\p_{r,\lambda}$ for the induced measure on $\Omega_{os} \times \prod_{t \in \Z} \R^\N$.  Then $\Lambda$ extends to a map $\Omega_{os} \times \prod_{t \in \Z} \R^\N \to \Omega_{os} \times \prod_{t \in \Z} \R^\N$ that preserves $\p_{r,\lambda}$ and $\p_{r,\lambda}$ is the unique extension such that the natural extension of $\Lambda$ has this property.

We can think of the element $\kappa_i(-t)$ as the increment that particle $i$ received $t$ steps in the past.  It is proved in \cite{A_GG07} that the sequence of random sequences $\big( (\kappa_i(-t) : i \in \N) : t \in \N \big)$ is weakly exchangeable conditional on $(\xi,Q)$.  Hence modulo establishing a first moment bound (Proposition 2.4, \cite {A_GG07}), it follows from the strong law of large numbers that the limit
\[ v_i(r,\lambda) = \lim_{T \to \infty} \frac{1}{T} \sum_{t=1}^T \lambda \kappa_i(-t)\]
exists almost surely; $v_i(r,\lambda)$ is referred to as the past velocity of particle $i$ under the evolution \eqref{eqn::qs} with $\psi(x) = \lambda x$ and $(\kappa_i)$ with covariance $Q^{*r}$.  Proposition 2.5 of \cite{A_GG07} gives that $v_i(r,\lambda) = v(r,\lambda)$ a.s., so that the past velocity of the particles is a.s. the same.  It is shown in Lemma 2.7 of \cite{A_GG07} that $v(r,\lambda)$ admits the explicit formula,
\begin{equation}
\label{eqn::past_velocity}
 v(r,\lambda) = \lambda \int_{-1}^1 (1-q^r) dx(q),
\end{equation}
where $x(q) = \E \sum_{i,j} \xi_i \xi_j 1_{\{q_{ij} \leq q\}}$.  Observe that $(r,\lambda) \mapsto v(r,\lambda)$ completely determines $x(q)$.  Using this we can show that the directing measure $\nu$ must be supported on a non-random sphere.

\begin{lemma}
\label{lem::dir_sphere}
If $(\xi,Q)$ is RQSE then its directing measure $\nu$ is supported in a non-random sphere.
\end{lemma}
\begin{proof}
Conditional on $Q$ and $\nu$, we know that there exists a sequence $(\phi_i)$ contained in $\supp \nu$ such that $q_{ij} = (\phi_i,\phi_j) + \delta_{ij} (1-\|\phi_i\|^2)$ that has the property that $\overline{\{\phi_i\}} = \overline{\{\phi_i : i \geq N\}}$ for every $N \in \N$.  In other words, removing a finite number of elements from the sequence $(\phi_i)$ does not change the closure of the corresponding set.  Let $\epsilon > 0$ be arbitrary.  Suppose that $j > i$ is such that
\[ \sup_{k > j} |q_{ik} - q_{jk} | = \sup_{k > j} |(\phi_i - \phi_j,\phi_k)| \leq \epsilon/4.\]
Since there exists $r > s > j$ such that $\|\phi_i - \phi_r\| \leq \epsilon/8$ and $\|\phi_j - \phi_s\| \leq \epsilon/8$, we have
\begin{align*}
          \| \phi_i - \phi_j \|^2
&\leq |(\phi_i - \phi_j, \phi_r)| + |(\phi_i - \phi_j, \phi_i - \phi_r)| + |(\phi_i - \phi_j, \phi_s)| + |(\phi_i - \phi_j, \phi_j - \phi_s)|\\
&\leq \epsilon.
\end{align*}
This implies that $\| \phi_i \|^2$ is determined completely by $q_{ij}$, $i \neq j$.  In particular, the length $\| \phi_i \|^2$ is intrinsic to the particle $\xi_i$.

Let $\epsilon > 0$ be arbitrary and let $\{\rho_k^2\}$ be an $\epsilon$-net of $[0,1]$.  Let $(\xi^k,Q^k)$ be the ROSt consisting of the particles $\xi_i$ such that $\rho_k^2$ is the largest point in the net smaller than $\| \phi_i \|^2$ normalized to have unit sum and $Q^k$ the corresponding overlap matrix (assuming non-empty).  Note that the event $(\xi^k,Q^k)$ is non-empty occurs with either probability $0$ or $1$ by ergodicity.  Furthermore, each non-empty $(\xi^k,Q^k)$ with probability $1$ has infinitely many particles as conditional on $\nu$ the $(\phi_i)$ are chosen iid.   Observe that $(\xi^k,Q^k)$ is RQSE as its correlated evolution is the evolution of $(\xi,Q)$ restricted to its own particles.  Let $v(r,\lambda)$ denote the velocity of $(\xi,Q)$ and $v^k(r,\lambda)$ the velocity of $(\xi^k,Q^k)$.  Then $v^k(r,\lambda) = v(r,\lambda)$ as the evolution of $(\xi^k,Q^k)$ is just the evolution of $(\xi,Q)$ restricted to $\xi^k$.  Hence it follows that $x^k(q) = \E \sum_{i,j} \xi_i^k \xi_j^k 1_{\{q_{ij}^k \leq q\}}$ is common among all of the non-empty ROSts $(\xi^k,Q^k)$ and equal to $x(q)$.  Therefore there can only be one $k_0$ such that $(\xi^{k_0},Q^{k_0})$ is non-empty.  This implies that $\supp \nu$ is contained in the annulus $\{ \phi \in \CH : \rho_{k_0}^2 \leq \| \phi\|^2 \leq \rho_{k_0}^2+ \epsilon \}$ and it follows from ergodicity that $\rho_{k_0}^2$ is constant.  Hence sending $\epsilon \to 0$ we see that $\nu$ is supported on a non-random sphere.
\end{proof}

\begin{lemma}
\label{lem::dir_det}
Suppose $(\xi,Q)$ is RQSE and directed by $\nu$.  Then the support of $\nu$ is countable.
\end{lemma}
\begin{proof}
By the previous lemma we know that $\nu$ is supported on a non-random sphere of radius $\rho^2$.  Conditional on $\nu$, let $(\phi_i)$ be a $\nu$-iid sequence so that $q_{ij} \stackrel{d}{=} (\phi_i,\phi_j)$, $i \neq j$.  Then $\phi_i = \phi_j$ if and only if $(\phi_i,\phi_j) = \rho^2$.  Let $q_2$ be the second largest element of $S_Q$ (which exists by our hypothesis on $Q$ and is deterministic by ergodicity).  Then if $\phi_i \neq \phi_j$, $(\phi_i,\phi_j) \leq q_2$.  Hence it follows that,
\[ \| \phi_i - \phi_j\|^2 = 2 \rho^2 - 2 (\phi_i,\phi_j) \geq 2 (\rho^2 - q_2) > 0\]
is strictly bounded from below so that the set of points $\{\phi_i : i \in \N\}$ in $\CH$ is discrete.  This can only happen if $\nu$ has countable support as $\CH$ is separable the sequence $(\phi_i)$ is iid.
\end{proof}

Theorems 1.9 and 1.10 of \cite{AA07} give that if $(\xi,Q)$ is RQSE then $\xi$ is distributed as a $PD(x,0)$ variable.  Hence if $\nu$ directs $(\xi,Q)$, conditional on $\nu$ we can view $(\xi,Q)$ as a marked $PD(x,0)$ variable $( (\xi_i,\phi_i) : i \in \N)$ with marking measure $\nu$.  One of the fundamental insights of \cite{AA07} (Lemma 2.7) is that the one step evolution of $(\xi,Q)$ under \eqref{eqn::qs} where $(\kappa_i)$ has covariance $Q^{*r}$ is also a marked $PD(x,0)$ random variable but with marking measure
\[ \nu'(d\phi) = \frac{e^{\lambda \kappa(T_r\phi)}}{N} \nu(d\phi).\]
Here, $N$ is a normalization so that $\nu'$ is a probability, $T_r \colon \CH \colon \to \CH$ is a map such that $(T_r \phi, T_r \psi) = (\phi,\psi)^r$, and $\kappa$ denotes an isomorphism of $\CH$ onto a Gaussian Hilbert space independent of $\xi$.  As $(\xi,Q)$ is RQS, the ROSt $(\xi,Q')$ with $Q'$ directed by $\nu'$ must have the same law as $(\xi,Q)$.  Hence we arrive at,

\begin{proposition}
\label{prop::rescale_direct}
Suppose $(\xi,Q)$ is a ROSt, $\xi \sim PD(x,0)$, directed by $\nu$.  Then $(\xi,Q)$ is RQS if and only if $\nu$ satisfies,
\begin{eqnarray}
\label{eqn::dir_eqn}
\nu(d\phi) \stackrel{d}{=} \frac{e^{\lambda \kappa(T_r \phi)}}{N} \nu(d\phi) \text{ for all } \lambda > 0, r \in \N
\end{eqnarray}
up to isometry of $\CH$.
In particular, if $S_Q \subseteq (-1,1)$, $0 < \alpha < (\sup S_Q)^{-1/2}$, and $f_\alpha \colon [-1,1] \to [-1,1]$ is the function
\[ f_\alpha(x) = \left\{ \begin{array}{cl} 1 \text{ for } x = 1\\ \alpha^2 x \text{ for } x \in (-1,1)\\ -1 \text{ for } x = -1 \end{array} \right.,\]
then $(\xi,f_\alpha(Q))$ is RQS for all $\lambda > 0$.
\end{proposition}
\begin{proof}
The first part is an immediate consequence of the above discussion; see also Theorem 4.2 of \cite{AA07}.  The second part follows from the scaling properties of \eqref{eqn::dir_eqn}.  Indeed, let $\nu'$ be given by scaling the support of $\nu$ by $\alpha$.  Then $\nu'$ satisfies,
\begin{align*}
     \nu'(d\phi)
&= \nu(d \alpha^{-1} \phi)
   \stackrel{d}{=} \frac{e^{\lambda \kappa(T_r  \alpha^{-1} \phi)}}{N} \nu( d \alpha^{-1} \phi)
 = \frac{e^{ \lambda \alpha^{-r} \kappa(T_r \phi)}}{N} \nu'(d\phi),
\end{align*}
up to isometry.
\end{proof}

Arguing as in \cite{AA07}, by Lemmas \ref{lem::dir_sphere} and \ref{lem::dir_det} we can associate with $\nu = \sum_j \eta_j \delta_{\psi_j}$ a \emph{directing ROSt} $(\eta,P)$ with $P = (p_{ij})$, $p_{ij} = (\psi_i,\psi_j)/ \sup S_Q$.  That $\nu$ satisfies \eqref{eqn::dir_eqn} implies $(\eta,P)$ is RQSE since the evolution of the weights $\eta = (\eta_n)$ under the $Q^{*r}$ evolution of $(\xi,Q)$ corresponds to,
\[ (\eta,P) \mapsto \left( \left(\frac{\eta_i e^{\lambda' \kappa_i}}{\sum_{j} \eta_j e^{\lambda'  \kappa_j}} \right)_\downarrow, P^\pi \right)\]
where $(\kappa_i)$ is a Gaussian sequence with covariance $P^{*r}$, $\lambda' =  \lambda(\sup S_Q)^{r/2}$.  Indeed, the argument is similar to the proof of Proposition 4.3 of \cite{AA07}.  One does have to be careful here since in principle it could be that $-1 \in S_P$.  This, however, leads to a contradiction since if $p_{ij} = -1$ then the future and hence past increments of particle $i$ are exactly $-1$ times those of $j$.  In particular, if $v(r,\lambda)$ denotes the $(r,\lambda)$-velocity with respect to the evolution of $(\eta,P)$, then $v_i(1,1) = -v_j(1,1)$ so that $v_i(1,1) = v_j(1,1) = v(1,1) = 0$ and it is clear from \eqref{eqn::past_velocity} that $v(1,1) > 0$.  If $|S_Q| = \infty$ and $\overline{S_Q}$ does not have limit points from below, then $\overline{S_P} = \overline{\{ q/ \sup S_Q : q \in S_Q \setminus \{\sup S_Q\}\}}$ also has this property.  Hence this procedure can be iterated arbitrarily many times.  In particular, $S_Q$ has an $n$th largest element $a_n$ that is necessarily non-negative; note that $a_n$ can be expressed in terms of the radii of the support of the first $n$ directing measures.  The idea of the proof of the following proposition is to combine this with the second part of the previous proposition to show that we can change the top of $S_Q$ while preserving the property of RQSE.  Let $X$ be the set of non-decreasing, right-continuous step functions $f$ on $[-1,1]$ satisfying $f(x) \leq x$ for every $x \in [-1,1]$ and fixing $-1$, $0$, and $1$.

\begin{proposition}
\label{prop::change_state_space}
Suppose $(\xi,Q)$ is RQSE, $|S_Q| = \infty$, $\overline{S_Q}$ does not have limit points from below, and $f \in X$.  Then $(\xi,f(Q))$ is RQSE and indecomposable.
\end{proposition}
Note that it is not \emph{a priori} clear that the matrix $f(Q)$ should even be positive semidefinite; this, however, will be immediate from the proof.  In the following, we say that $(\xi,Q)$ is directed by $(\eta,P)$ with scaling factor $\rho$ provided $\xi$ is independent of $(\eta,P)$ and conditional on $(\eta,P)$, $q_{ij} \stackrel{d}{=} \rho p_{i^* j^*}$, $ i \neq j$, where $(i^*)$ is a sequence of $\eta$-iid random integers.
\begin{proof}
Let $a_n \geq 0$ be the $n$th largest element of $S_Q$.  Suppose that $g \colon [-1,1] \to [-1,1]$ is any right-continuous non-decreasing function such that $g(1) = 1$, $g(x) = x$ for all $x < a_N$ for some fixed $N \in \N$, and $g|[x,1]$ has finite range.    Our first claim is that $(\xi,g(Q))$ is RQSE.  To see this, let $\nu_1$ be the directing measure of $(\xi,Q)$ and $(\xi^1,Q^1)$ the associated directing ROSt.  Inductively let $\nu_k$ direct $(\xi^{k-1},Q^{k-1})$ for each $k \geq 2$.  Choose $\alpha_1,\ldots,\alpha_{N+1} \geq 0$ so that $\alpha_1 = g(a_1)$, $\alpha_1 \alpha_2 = g(a_2),\ldots, \alpha_1 \cdots \alpha_{N} = g(a_N)$ and $\alpha_1 \cdots \alpha_{N+1} = a_{N+1} < g(a_N)$.  Inductively set $(\xi^{k},P^k)$ to be the ROSt directed by $(\xi^{k+1},P^{k+1})$ with scaling factor $\alpha_{k+1}$ for $0 \leq k \leq N$ and $P^{N+1} = Q^{N+1}$.  Then $(\xi,P) = (\xi^0,P^0) = (\xi,g(Q))$, which proves the claim.

Let $\CA$ be the set of ROSts that are RQS,
\[ g_\alpha(x) = \left\{ \begin{array}{cl} f(x) \vee \alpha \text{ for } x \geq \alpha\\ x \text{ for } x < \alpha \end{array}\right. ,\]
and $A = \{ \alpha \in [-1,1] : (\xi,g_\alpha(Q)) \in \CA\}$.  The previous part gives us that $A \neq \emptyset$.  As $\CA$ is closed (Proposition \ref{prop::rqs_closed}) and, as $f \in X$, $\alpha \mapsto (\xi,g_\alpha(Q))$ is continuous hence $A$ is closed.  We just need to show that $A$ is open.  Suppose $\alpha \in A$ so that $(\xi,g_\alpha(Q)) \in \CA$.  The case when $|S_{g_\alpha(Q)}| < \infty$ is trivial.  Suppose $|S_{g_\alpha(Q)}| = \infty$.  As $(\xi,Q)$ is ergodic it follows that $(\xi,g_\alpha(Q))$ is as well and hence is RQSE.  Furthermore, $\overline{S_{g_\alpha(Q)}}$ does not have limit points from below.  Therefore $S_{g_\alpha(Q)}$ has an $n$th largest element $b_n \geq 0$ for every $n$.  As $g_\alpha$ takes on only a finite number of values for $x \geq \alpha$, there exists $N$ large enough so that $b_N < \alpha$.  Hence if $|\beta - \alpha| < \alpha - b_N$, $\beta \in A$.  Therefore $A$ is open, so that $A = [-1,1]$.

An immediate consequence of Lemma \ref{lem::dir_sphere} and an easy induction argument is that every RQSE ROSt with finite state space is indecomposable.  Hence the last part of the proposition follows.
\end{proof}

\noindent We can now prove Theorem \ref{thm::main_theorem}.

\begin{proof}[Proof of Theorem \ref{thm::main_theorem}]
Suppose $(\xi,Q)$ is RQSE.  By Proposition \ref{prop::change_state_space}, $(\xi,f(Q))$ is also RQSE and indecomposable with $f \in X$ provided $-1 < f(x) < 1$ for $x \in (-1,1)$.  Letting $\epsilon > 0$ be arbitrary we can choose such $f$ so that $d((\xi,Q),(\xi,f(Q))< \epsilon$.  By Theorem 1.8 of \cite{AA07} $(\xi,f(Q))$ is given by a finite level RPC.  By the discussion following Proposition \ref{prop::rpc_homeo}, we know that the closure of the set of RPCs with fixed Poisson-Dirichlet parameter is the set of continuous RPCs with the same parameter.  Therefore $(\xi,Q)$ is a continuous RPC.
\end{proof}

\section*{Acknowledgments}
I would like to thank Amir Dembo and Andrea Montanari for teaching a course in spin-glass models at Stanford University in the winter of 2008 that led to the this research problem as well as providing invaluable guidance in the preparation of this article.  I would also like to thank Louis-Pierre Arguin for helpful discussions and e-mail correspondence.

\bibliographystyle{plain.bst}
\bibliography{qs_references}

\end{document}

config: arxiv


TITLE: Rolle's Theorem on a derivative...
QUESTION [2 upvotes]: I have the following:
Suppose $p(x) =(x^{2}-1)^{m}$ for some $m \geq2$.
Applying Rolle's Theorem on each of the intervals $[-1,c]$ and $[c,1]$, show that $p''(x)$ has at least two roots in $(-1,1)$.
By induction, prove that for $k=1,2,\ldots,m$ the $k$-th derivative $p^{(k)}(x)$ has at least $k$ distict real roots lying in the interval $(-1,1)$.
I have first of all shown that for $p'(x)$ that there is a root in $(-1,1)$, but struggling with the other two parts, any help would be most appreciated.

REPLY [1 votes]: We have that $$p(x) = (x^2-1)^m$$ Note we need $m >2$.
Taking derivatives we have
$$p'(x)=2xm(x^2-1)^{m-1}$$
$$p''(x)=4x^2m(m-1)(x^2-1)^{m-2}+2m(x^2-1)^{m-1}$$
Rolle's Theorem asserts that if $f(x)$ is continuous in $I=[a,b]$ and $f(a)=f(b)$, then there is a $c \in I$ such that
$$f'(c)=0$$
We have that $f(-1) = f(1)$, so there is a $c$ such that $f'(c)=0$. We can immediatelly see such $c$ is $c=0$.
Moreover, we see that $f'(-1) = f'(1)=0$, but since $f'(0)=0$, we can assert that there exists $c_1 \in (-1,0)$ and $c_2 \in (0,1)$ such that $f''(c_1)=f''(c_2)=0$. Note that if $m=1,2$ the test would fail, since the first (third) derivative is a line.
You want to prove now that for $k=1,2,3,\dots ,m$, it is the case $p^{(k)}(c_i)=0$ for $i=1,2,\dots, m  \in (-1,1) $. The induction hypothesis would then be:
$\mathcal H.$ It is true that $p^{(k)}(c_i)=0$ for $i=1,2,\dots,k  \in (-1,1) $
This means that $p^{(k)}(c_1) = p^{(k)}(c_2) = \cdots = p^{(k)}(c_i)=0$. Since we also have two more roots, namely $1$ and $-1$, then we can assert by Rolle's Theorem, that $p^{(k+1)}(x)$ will have $n=k+2-1=k+1$ roots. Since $k=2$ is true, this completes the induction phase.


TITLE: Two continuous functions over a closed, bounded and Jordan-Measurable set: Show that its graph Jordan-Measurable
QUESTION [1 upvotes]: Let f,g: $A\subset\mathbb{R}^{n}\mapsto\mathbb{R}$ continuous functions over the Jordan-measurable, bounded and closed set A, such that  $f(x)\leq g(x) \forall x\in A$ Show that $B=\{(x,y)\in\mathbb{R}^{n+1}|f(x)\leq y \leq g(x)\}$ is Jordan-measurable in $\mathbb{R}^{n+1}$
I have problems with the proof. I don't know how to complete this but we know that if the function is continuous, then f is uniformly continuous, then for every $\epsilon>0$ there is a $\delta>0$ such that if $|x-y|<\delta \implies |f(x)-f(y)<\epsilon|$.Then maybe we can cover the graph with a finite number of rectangles but, to use this argument I must prove that the graph is continuous I guess... I will appreciate any help to end this proof because I'm a little lost.

REPLY [1 votes]: It is enough to show that the Jordan measure of the boundary of this set is $0$. Now the boundary of the set is included in $(\partial A\times [m,M]) \cup \Gamma_f\cup \Gamma_g$.
Let's show that $m(\Gamma_f)$  ( the Jordan measure of the graph of $f$) is $0$. Indeed, $A\subset C$ where $C$ is a fixed cube. Divide $C$ into small cubes so that the variation  of $f$ over any $c\cap A$ is smaller that $\epsilon$. We get that $\Gamma_f\subset $ a finite cover of $n+1$-dim cubes of total measure $<\epsilon \cdot m(C)$.
Added:Take $\delta$ so that $|x-y|< \delta \implies |f(x)-f(y)|< \epsilon$. Now divide $D$ into small cubes of diameter $<\delta$. For any $x,y \in c\cap A$ we have $f(x)-f(y)< \epsilon$. It follows that $0\le \sup f(c\cap A)- \inf f(c\cap A)\le \epsilon$. Therefore, $f(c\cap A)$ is contained in a closed interval $I_c$ of length $\epsilon$. So the piece of the graph of $f$ over $c\cap A$ is contained in $c\times I_c$ which has a measure $\le m(c)\times \epsilon$.


TITLE: Why does the recursion $x_{n+1} = f(x_n)$ with $f(x) = p^k\cdot\sqrt[k+1]{x}$ converge to $p^{k+1}$?
QUESTION [0 upvotes]: Why does the recursion $x_{n+1} = f(x_n)$ with $f(x) = p^k\cdot\sqrt[k+1]{x}$ converge to $p^{k+1}$?

In addition, how can you write a function that has rational or integer fixed points? For example, you get $k^2$ as a fixed point of $f(x)=k\sqrt{x}$. Is there any known way to work back from an integer/rational number, and basically construct a function with said number as a fixed point?

REPLY [0 votes]: Apparently, the solution is easier solved algebraically. Just let $x=p^{k}\cdot x^{\frac{1}{k+1}}$. Raising both sides by $k+1$ gives:
$$\frac{x^{k+1}}{x}=p^{k(k+1)}$$
$$x^k=p^{k(k+1)}$$
$$x=p^{k+1}$$


TITLE: Is a sequence of disjointly supported functions in $L^\infty$ complemented?
QUESTION [5 upvotes]: Let $(f_n)_{n \geq 1}$ be disjointly supported sequence of functions in $L^\infty(0,1)$. Is the space $\overline{\mathrm{span}(f_n)}$ (the closure of linear span) complemented in $L^\infty(0,1)$? By complemented we mean that $L^\infty(0,1) = \overline{\mathrm{span}(f_n)} \oplus X$, where $X$ is a subspace of $L^\infty$ and $\oplus$ is direct sum.
Equivalently, we can ask if there exists a projection $P\colon L^\infty(0,1) \to \overline{\mathrm{span}(f_n)}$?
It is quite easy to prove this in $C[0,1]$. Indeed, let $(f_n)$ be disjointly supported sequence in $C[0,1]$ and fix $x_n \in \mathrm{supp}(f_n)$, $n \in \mathbb{N}$. Then the space $C[0,1]$ can be written as
$$
C[0,1] = \overline{\mathrm{span}(f_n)} \oplus \{f \in C[0,1]\colon f(x_n) = 0, n = 1,2,\dots \}.
$$

REPLY [1 votes]: If all but finitely many of the functions are the zero function, then the answer is yes, because any finite-dimensional subspace is complemented.  But this is the trivial case.
In the nontrivial case, just note that if you normalize the nonzero functions in the sequence, they form a basic sequence $1$-equivalent to the unit vector basis of $c_0$.  But we know $\overline{\text{span}(f_n)}=c_0$ is not complemented in $L_\infty=\ell_\infty$ (see, for example, Albiac and Kalton's Topics in Banach Space Theory).


TITLE: How to prove this argument valid?
QUESTION [3 upvotes]: I was just wondering if some helpful person wouldnt mind helping me with this discrete maths question that has had be stuck for about a day now.
The argument is:
p or q
q implies ~p
q implies r
conclusion: r

I cant for the life of me figure out how to prove this.
Thanks heaps for any help you can give.
Thanks
Corey

REPLY [2 votes]: We can apply Resoulution to the three clauses (the premises) :

1) $p \lor q$
2) $\lnot q \lor \lnot p$ (equivalent to : $q \to \lnot p$)
3) $\lnot q \lor r$ (equivalent to : $q \to r$)

and the negation of the purported conclusion :

4) $\lnot r$.

Applying the procedure we get :
i) $p \lor r$ --- from 1) and 3)
ii) $\lnot q \lor r$ --- from i) and 2)
iii) $\lnot q$ --- from ii) and 4).
We have concluded the procedure without having derived the empty clause; thus, the argument is invalid.


TITLE: Weak Equivalence between an arbitrary space and a CW complex
QUESTION [1 upvotes]: When working in the compactly generated spaces (weak Hausdorff $k$-spaces) it is true that any space is weakly equivalent to a CW complex. I'm interested in the converse: let $X$ be a CW complex and $Y$ be a topological space such that there is a weak equivalence $X \to Y$, then is it necessarily true that $Y$ is compactly generated? If that is not true in general, does it hold for homotopy equivalence? I figure the proof would be an abysmal exercise in point-set topology if either were true.
I wondered about this while trying to show that a certain space does not have the homotopy type${}^*$ of a CW complex, and that if one wanted to look for such a space one shouldn't waste any time looking in the category of compactly generated spaces. If the above were true I could prove no such weak equivalence exists if the space isn't compactly generated.
${}^*$It seems some authors take homotopy type to mean weak equivalence, which makes sense in the category of CW spaces, but in general is homotopy type taken to mean homotopy equivalence?

REPLY [3 votes]: Every space is weak equivalent to a CW-complex; in fact, I'm not familiar with any proof that only compactly generated spaces (as opposed to all spaces) are weak equivalent to CW-complexes.  For instance, the proof in Hatcher (Proposition 4.13) works for all spaces.
In any case, if you know the result for $k$-spaces, you can immediately deduce it for arbitrary spaces, since the map $kX\to X$ to any space from its $k$-ification is a weak equivalence (this is immediate from the fact that "weak equivalence" is defined in terms of maps from certain compact Hausdorff spaces to $X$).
For strong homotopy type, however, compact generation is neither necessary nor sufficient to be homotopy equivalent to a CW-complex.  For instance, if $X$ is any non-compactly generated space, the cone on $X$ is contractible and hence homotopy equivalent to a CW-complex, but not compactly generated.  On the other hand, plenty of compact Hausdorff spaces such as $\{0\}\cup\{1,1/2,1/3,\dots\}$ are not homotopy equivalent to CW-complexes.


TITLE: Prove that $\frac{\sqrt{3}}{8}<\int_{\frac{\pi}{4}}^{\frac{\pi}{3}}\frac{\sin x}{x}\,dx<\frac{\sqrt{2}}{6}$
QUESTION [6 upvotes]: Prove that $$\frac{\sqrt{3}}{8}<\int_{\frac{\pi}{4}}^{\frac{\pi}{3}}\frac{\sin x}{x}\,dx<\frac{\sqrt{2}}{6}$$

My try: Using $$\displaystyle \sin x<x$$ and $$\frac{\sin x-0}{x-0}>\frac{1-0}{\frac{\pi}{2}-0}=\frac{2}{\pi}$$
So we get $$\frac{2}{\pi}<\frac{\sin x}{x}<1$$
So we get  $$\frac{2}{\pi}\int_{\frac{\pi}{4}}^{\frac{\pi}{3}}1\,dx<\frac{\sin x}{x}<1\cdot \int_{\frac{\pi}{4}}^{\frac{\pi}{3}}\,$$
But this is not what I have to prove here.

REPLY [6 votes]: This is not an answer but it is too long for a comment.
I cannot resist the pleasure of reporting again the magnificent approximation proposed by Mahabhaskariya of Bhaskara I, a seventh-century Indian mathematician.$$\sin(x) \simeq \frac{16 (\pi -x) x}{5 \pi ^2-4 (\pi -x) x}\qquad (0\leq x\leq\pi)$$ (see here).
So, as an approximation $$\int\frac{\sin(x)}x dx\approx-2 \left(\log \left(4 x^2-4 \pi  x+5 \pi ^2\right)+\tan
   ^{-1}\left(\frac{1}{2}-\frac{x}{\pi }\right)\right)$$ which gives $$\int_{\frac{\pi}{4}}^{\frac{\pi}{3}}\frac{\sin x}{x}dx\approx 2 \log \left(\frac{153}{148}\right)+\tan ^{-1}\left(\frac{100}{621}\right)\approx 0.226111$$ while the exact solution is $$\int_{\frac{\pi}{4}}^{\frac{\pi}{3}}\frac{\sin x}{x}dx=\text{Si}\left(\frac{\pi }{3}\right)-\text{Si}\left(\frac{\pi }{4}\right)\approx 0.226483$$ your bounds being $\approx 0.216506$ and $\approx 0.235702$


text:
\begin{document}

\maketitle

\begin{abstract}
In this paper, we propose a novel accelerated stochastic gradient method with momentum, which momentum is the weighted average of previous gradients. The weights decays inverse proportionally with the iteration times. Stochastic gradient descent with momentum (Sgdm) use weights that decays exponentially with the iteration times to generate an momentum term.
Using exponentially decaying weights, variants of Sgdm with well designed and complicated formats have been proposed to achieve better performance.
The momentum update rules of our method is as simple as that of Sgdm.
We provide theoretical convergence properties analyses for our method, which show both the exponentially decay weights and our inverse proportionally decay weights can limit the variance of the moving direction of parameters to be optimized to a region.
Experimental results empirically show that our method works well with practical problems and outperforms Sgdm, and it outperforms Adam in convolutional neural networks.
\end{abstract}
\begin{keywords}
exponential decaying rate weight, gradient descent,  inverse proportional decay rate weight, momentum
\end{keywords}

\section{Introduction}

A stochastic optimization problem can be consider as minimizing a differentiable function $F: \mathbb{R}^d \rightarrow \mathbb{R}$ using stochastic gradient descent (SGD) optimizer over a data set $\mathcal{S}$ which has $n$ samples. Function $F(x_k)$, in the empirical risk format, can be written as $F(x_k) = \frac{1}{n}\sum_{i=1}^{n}f_i(x_k)$, where $f_i(x_k)$ is the realization of $F(x_K)$ with the $i$th sample. Given the initial $x_0$ and a stepsize $\alpha_{k=0} >0$, the optimizer iterates with the following rule
\begin{equation}
x_{k+1} \leftarrow x_k - \alpha_kg_i(x_k),
\end{equation}
until $F(x_k)$ reaches a predefined state.
The vector $g_i(x_k)$ is the stochastic gradient of $f_i(x)$, which gradient satisfies $\mathbb{E}[g_i(x_k)] = \nabla F(x_k)$ and has bounded variance~\cite{bottou2018}. For large-scale data sets, the computational complexity of iterating with full gradient $F(x) = \frac{1}{n}\sum_{i=1}^{n}$ is unacceptable. It is more efficient to measure a single component gradient $\nabla f_{i}(x_k)$, where $i$ is the index of the uniformly selected sample from the $n$ samples, and move in the noisy direction $g_i(x_k) = \nabla f_{i}(x_k)$, than to move in the full gradient direction $\nabla F(x_k) = \frac{1}{n}\sum_{i=1}^{n}\nabla f_{i}(x_k)$ with a bigger stepsize~\cite{adagradstepsize,bottou2018}. However, choosing a feasible and suitable stepsize schedule $\{\alpha_k>0\}$ is difficult.
According to the work of Robbins and Monro~\cite{robbins1951}, the stepsize schedule should satisfy
\begin{equation}
\sum_{k=1}^{\infty}\alpha_k = \infty \quad \text{and} \quad \sum_{k=1}^{\infty}\alpha_k^2 < \infty
\end{equation}
to make $\lim_{k\rightarrow\infty}\mathbb{E}[\|\nabla F(x_k)\|^2] = 0$. This constraint makes full gradient descent methods converge slower than stochastic SGD methods.

Methods using gradients in previous iterations as momentum terms have been proposed to accelerate the convergence and show great benefits~\cite{adam,sgdm}. Yet, theoretical analyses of those method in stochastic settings are elusive, and the ways to generate the momentum term from previous gradients can be revised.

\subsection{Stochastic Gradient Methods With Momentum}
Stochastic gradient descent methods with momentum (Sgdm) update parameter $x$ with
\begin{equation}
x_{k+1} \leftarrow x_k - \alpha_kg_k(x_k) + \gamma m_k,
\label{sgdm_x}
\end{equation}
where $m_k$ is called a momentum term, and Sgdm updates the momentum term with
\begin{equation}
m_{k} = \gamma m_{k-1} - \alpha_{k-1} g_k(x_{k-1}).
\label{sgdm_m}
\end{equation}
If $\gamma$ is a constant, then we call it a exponentially decay rate. With~(\ref{sgdm_m}), we can rewrite the update rule~(\ref{sgdm_x}) as
\begin{equation}
x_{k+1} = x_k + \sum_{j=1}^{k}\alpha_j\gamma^{k-j}g_{j}(x_j),
\label{x_update}
\end{equation}
which shows that the moving direction here is a weighted average of all gradients, with exponential decay weights. We denote the weighted average of gradients as $v_k = \sum_{j=1}^{k}\alpha_j\gamma^{k-j}g_{j}(x_j)$. It is believed that the momentum term can reduce the variance~\cite{initialization2013}. Using a exponential decay rate is common and effective. According our following analyses, a exponential decay rate can limit the variance of $v_k$ to a region which determined by the constant $\gamma$.

{\bf Main Contribution}
First, we proposed a novel stochastic gradient descent method with inverse proportional decay rate momentum, which method dynamically adjusts the momentum to match the convergence of the stochastic optimization problem. Besides, our rigorous analyses prove that both the simple SGDM and our novel momentum term can limit the variance to a region $\gamma$ (Theorem~\ref{theorem2},Theorem~\ref{theorem3}). We list out two main theorems (informally) in the following.

For a differential function $F$ with $L$-Lipschitz gradient and the variance of gradient is limited,  Theorem~\ref{theorem2} implies that the momentum term with exponentially decay weights can limit the variance of $v_k$
\begin{displaymath}
\mathbb{V}[v_k]\le\frac{1}{1-\gamma^2}\alpha_0^2(M+2M_V(\|\nabla F(x_k)\|_2^2 + L^2D^2)).
\end{displaymath}
Theorem~\ref{theorem3} implies that the momentum term with our inverse proportional decay weights can limit the variance of $v_k$
\begin{displaymath}
\mathbb{V}[v_k]\le\frac{\alpha_0^2}{2\beta}\Big(M+2M_V\|\nabla F(x_k)\|_2^2+2M_VL^2D^2\Big).
\end{displaymath}

Extensive experiments in Section 4 shows that the robustness of our method extends from linear regression to practical model in deep learning problems.

\subsection{Previous Work}
Momentum method and its use within optimization problems has been studied extensively ~\cite{initialization2013, o1996, sgdm}. The classical momentum (CM) method ~\cite{polyak} accumulates a decaying sum of the previous updates of parmeter $x$ into a momentum term $m$ using equation~(\ref{sgdm_m}) and updates $x$ with~(\ref{sgdm_x}). CM uses constant hyperparameter $\gamma$ and learning rate $\alpha$. With this method, one can see that the steps tend to accumulate
contributions in directions of persistent descent, while directions that oscillate tend
to be cancelled, or at least remain small~\cite{bottou2018}. Thus, this method can make optimization algorithms move faster along dimensions of low curvature where the update is small and its direction is persistent and slower along turbulent dimensions where the update usually significantly changes its direction ~\cite{initialization2013}.
The adaptive momentum method in~\cite{sgdm} uses decaying learning rate and adaptive $\beta = \max(0, 1- \alpha_0 \mu^2)$, where $\mu(t)$ is the network input at time $t$.
\subsection{Our Method}

Our method updates $x_k$ with
\begin{equation}
x_{k+1} \leftarrow x_k - \alpha_k g_{k}(x_k) + \gamma(k)m_k, \label{x_novel_update}
\end{equation} and it updates the momentum term $m_K$ with
\begin{equation}
m_k \leftarrow \gamma(k-1)m_{k-1} - \alpha_{k-1}g_{k-1}(x_{k-1}), \label{m_novel_update}
\end{equation} where
\begin{equation}
y(k) = \left(\frac{k}{k+1}\right)^\beta.
\label{gamma_novel_update}
\end{equation}
The hyperparameter $\beta$ is a predefined constant. Thus we can rewrite the updating rules (\ref{x_novel_update}),(\ref{m_novel_update}), and (\ref{gamma_novel_update}) as
\begin{displaymath}
x_{k+1} \leftarrow x_k - \sum_{i=1}^{k}\alpha_ig_i(x_i)\left(\frac{i}{k}\right)^\beta.
\end{displaymath}
We denote the moving direction of $x_k$ as $v_k =- \sum_{i=1}^{k}\alpha_ig_i(x_i)\left(\frac{i}{k}\right)^\beta$.

We use the same stepsize as shown in (adam)
\begin{equation}
	\alpha_i = \frac{\alpha_0}{\sqrt{i}}
	\label{stepsize}
\end{equation}
And it is straightforward that $\sum_{i}^{\infty}\alpha_k = \infty$.

\begin{algorithm}[tb]
	\caption{Our method}
	\label{algorithm}
	\begin{algorithmic}
		\STATE{\bfseries Require:} Stepsize $\alpha$
		\STATE{\bfseries Require:} Factor of decay rates, $\beta$
		\STATE{\bfseries Require:} Stochastic objective function $f(x)$
		\STATE{\bfseries Require:} Initial parameter vector $x_0$
		\STATE Initialize momentum vector $m_0\leftarrow0$
		\STATE Initialize iteration times $k\leftarrow0$
		\REPEAT
		\STATE $k \leftarrow k+1$
		\STATE $\alpha_{k} \leftarrow \frac{\alpha_0}{\sqrt{k}}$
		\STATE Generate gradient vector $g_k\leftarrow \nabla_x f_k(x_{k-1})$
		\STATE $m_k \leftarrow \gamma(k) m_{k-1} - \alpha_{k}g_k$
		\STATE $x_k \leftarrow x_{k-1} + m_k$
		\UNTIL{predefined conditions are achieved}
		\RETURN $x_k$
	\end{algorithmic}
\end{algorithm}

\section{Algorithm}
See Algorithm~\ref{algorithm} for the pseudo-code of our proposed algorithm. We denote $f(x)$ as a risk function with noise, which is differentiable with respect to parameters $x$. The optimization problem is to minimize the expected risk function $\mathbb{E}[f(x)]$ with respect to parameters $x$. We denote $f_1(x),\dots,f_T(x)$ as the realizations of the risk function at subsequent iterations $1,\dots,T$. Let $g_t = \nabla_x f_t(x)$ be the gradient of $f_t(x)$ with respect to $x$ in the $t$th iteration.

Our algorithm updates weighted averages of the previous gradients, denoted as $m_k$. The hyper-parameter $\beta\in(1,\infty)$ control the decay rates of the weighted averages. We initialize $m_k$ as a vector with all 0 elements.

\section{Convergence Analysis}
In this section, we show that the momentum term could reduce the variance of stochastic directions $v_k$ along the iterations progress. A fixed exponential decay factor $\gamma$ and a changing factor $\gamma(k)$ can both limit the variance within a small range.

Let us begin with a basic assumption of smoothness of the objective function.

\newtheorem{assumption}{Assumption~}[section]

\begin{assumption}[Lipschitz-continuous gradients]\label{ac:ass:lcg}
	The objective function $F: \mathbb{R}^d\rightarrow \mathbb{R}$ is continuously differentiable and the gradient function of $F$, namely, $\nabla F:\mathbb{R}^d\rightarrow\mathbb{R}^d$, is Lipschitz continuous with Lipschitz constant $L>0$, i.e.,
	\begin{equation*}
	\|\nabla F(x)-\nabla F(\bar{x})\|_2\le L\|x-\bar{x}\|_2
	~~\textrm{for all}~~\{x, \bar{x}\}\subset\mathbb{R}^d.
	\end{equation*}
\end{assumption}

\iffalse
{\bf Assumption 3.1}~(Lipschitz-continuous objective gradients). {\it The objective function $F: \mathbb{R}^d\rightarrow \mathbb{R}$ is continuously differentiable and the gradient function of $F$, namely, $\nabla F:\mathbb{R}^d\rightarrow\mathbb{R}^d$, is Lipschitz continuous with Lipschitz constant $L>0$, i.e.,
	\begin{displaymath}
	\|\nabla F(x) - \nabla F(\bar{x}) \|_2\le L\|x - \bar{x}\|_2,\; for\; all\; \{x, \bar{x}\}\subset\mathbb{R}^d.
	\end{displaymath}   }
\fi

Assumption~3.1 is essential for convergence analyses of most gradient-based methods, which ensures that the gradient of $F$ does not change arbitrarily quickly with respect to the parameter vector $x$. Based on Assumption~3.1, we have
\begin{equation}
F(x)\le F(\bar{x}) + \nabla F (\bar{x})^T(x- \bar{x}) + \frac{1}{2}L\|x - \bar{x}\|_2^2,
\label{lip_inequal}
\end{equation}
which inequality holds for all $\{x, \bar{x}\}\subset\mathbb{R}^d$.

\begin{proof}
	Using Assumption 3.1, we have
	\begin{displaymath}
	\begin{aligned}
	F(x) &= F(\bar{x}) + \int_0^1\frac{\partial F(\bar{x}+t(x - \bar{x}))}{\partial t}dt\\
	&= F(\bar{x}) + \int_0^1\nabla F(\bar{x}+t(x-\bar{x}))^T(x-\bar{x})dt\\
	&=F(x) + \nabla F(\bar{x})^T(x-\bar{x}) +\int_0^1[\nabla F(\bar{x}) + t(x - \bar{x}) -\nabla F(\bar{x})]^T(x - \bar{x})dt \\
	&\le F(\bar{x}) + \nabla F(\bar{x})^T(x-\bar{x}) + \int_0^1 L \|t(x-\bar{x})\|_2\|x-\bar{x}\|_2dt,
	\end{aligned}
	\end{displaymath}
	from which the desired result follows.
	\end{proof}

\subsection{Variance Analysis}
We first consider a fixed decay factor $\gamma\in(0,1)$, which is used in many simple stochastic gradient descent methods with momentum.

\begin{assumption}\label{ac:ass:var}
	The objective function F and stochastic gradient $g_k(x_k)$ satisfy for all $k \in \mathbb{N}$, there exist scalars $M\ge0$ and $M_v \ge 0$ such that
	\begin{equation*}
	\mathbb{V}_{x_k}[g_i(x_k)] \le M + M_V\|\nabla F(x_k)\|_2^2.
	\end{equation*}
\end{assumption}

\begin{theorem}\label{theorem1}
	Under Assumptions \ref{ac:ass:lcg} and \ref{ac:ass:var}, suppose that the algorithm 1 satisfies $\|x_i-x_j\|\leqslant D$ for any $i,j\in\mathbb{N}$. Then
	\begin{equation*}
	\|\nabla F(x_j)\|_2^2\leqslant2\|\nabla F(x_k)\|_2^2+2L^2D^2.
	\end{equation*}
	\end{theorem}

\begin{proof}
	According to Assumption \ref{ac:ass:lcg}, there is a diagonal matrix $\Lambda= \mathrm{diag}(\lambda_1,\cdots,\lambda_d)$ with $\lambda_i\in [-L,L]$ such that
	\begin{align*}
	\nabla F(x_j)=\nabla F(x_k+\delta_{j,k})=\nabla F(x_k)+\Lambda\delta_{j,k},
	\end{align*}
	where $x_j=x_k+\delta_{j,k}$; and by further noting that $\|\delta_{j,k}\|_2=\|x_j-x_k\|_2\leqslant D$, we have
	\begin{align*}
	\|\nabla F(x_j)\|_2^2\leqslant&\Big(\|\nabla F(x_k)\|_2
	+L\|\delta_{j,k}\|_2\Big)^2 \\
	\leqslant&\|\nabla F(x_k)\|_2^2+L^2\|\delta_{j,k}\|_2^2
	+2L\|\delta_{j,k}\|_2\|\nabla F(x_k)\|_2 \\
	\leqslant&2\|\nabla F(x_k)\|_2^2+2L^2\|\delta_{j,k}\|_2^2 \\
	\leqslant&2\|\nabla F(x_k)\|_2^2+2L^2D^2
	\end{align*}
	as claimed.
\end{proof}

\begin{theorem}[a fixed decay factor]\label{theorem2}
	Under the conditions of Theorem~\ref{theorem1} and Assumption~\ref{ac:ass:var}, suppose that (i) the sequence of iterates $\{x_k\}$ is generated with (\ref{x_update}) using a fixed factor $\gamma \in (0,1)$ and a stepsize sequence $\{\alpha_k\}$, which sequence satisfies  $\alpha_k \ge \alpha_{k+1}$ for all $k \in \mathbb{N}$, and (ii) the sequence $\{x_k\}$ satisfies $\|x_i - x_j\|\le D$ for any $i,j\in\mathcal{N}$, then
	\begin{displaymath}
	\mathbb{V}[v_k]\le \frac{1}{1-\gamma^2}\alpha_0^2\big(M+2M_V\|\nabla F(x_k)\|_2^2+2M_VL^2D^2\big)
	\end{displaymath}
\end{theorem}
\begin{proof}
	For the SGDM updating strategy, we have direction vector
	\begin{displaymath}
		 v_k = -\sum_{i=1}^{k}\alpha_i\gamma^{k-i} g_i(x_i).
	\end{displaymath}
	Hence, along with Assumption \ref{ac:ass:var}, we obtain
	\begin{align*}
	\mathbb{V}[v_k]=&\sum_{j=1}^k\gamma^{2(k-j)}\alpha_j^2
	\mathbb{V}_{x_j}[g_j(x_j)] \\
	\leqslant&\alpha_0^2\sum_{j=1}^k\gamma^{2(k-i)}
	\Big(M+M_V\|\nabla F(x_j)\|_2^2\Big) \\
	\leqslant&\sum_{i=1}^k\alpha_0^2\gamma^{2(k-i)}
	\Big(M+2M_V\|\nabla F(x_k)\|_2^2+2M_VL^2D^2\Big).
	\end{align*}
	Notice that
	\begin{align*}
	\sum_{j=1}^k\gamma^{2(k-j)}=\frac{1-\gamma^{2k}}{1-\gamma^2}.
	\end{align*}
	Since $\frac{1-\gamma^{2k}}{1-\gamma^2}$ decays to $\frac{1}{1-\gamma^2}$ as $k$ increases for $0<\gamma<1$, so the variance of $v_k$ could be finally reduced to
	\begin{equation*}
	\frac{1}{1-\gamma^2}\alpha_0^2\Big(M+2M_V\|\nabla F(x_k)\|_2^2+2M_VL^2D^2\Big).
	\end{equation*}
\end{proof}

\begin{theorem}[a changing decay factor]\label{theorem3}
	Under the conditions of Theorem~\ref{theorem1} and Assumption~\ref{ac:ass:var}, suppose that (i) the sequence of iterates $\{x_k\}$ is generated with (\ref{x_novel_update}) using a changing factor $\gamma(k) \in (0,1)$ taking the form $\gamma_k = (k/k+1)^\beta$ and a stepsize sequence $\{\alpha_k\}$ as (\ref{stepsize}), which sequence satisfies  $\alpha_k \ge \alpha_{k+1}$ for all $k \in \mathbb{N}$, and (ii) the sequence $\{x_k\}$ satisfies $\|x_i - x_j\|\le D$ for any $i,j\in\mathcal{N}$, then
	\begin{displaymath}
	\mathbb{V}[v_k]\le \frac{\alpha_0^2}{2\beta}\Big(M+2M_V\|\nabla F(x_k)\|_2^2+2M_VL^2D^2\Big)
	\end{displaymath}
\end{theorem}
\begin{proof}
	For our updating strategy
	\begin{displaymath}
	v_k = -\sum_{j=1}^{k}\frac{j^\beta}{k^\beta}\alpha_jg_j(x_j)
	\end{displaymath}
	Hence, along with Assumption \ref{ac:ass:var}, we obtain
	\begin{align*}
	\mathbb{V}[v_k]=&\alpha_0\sum_{j=1}^k\frac{j^{2\beta}}{k^{2\beta}}\frac{1}{j}
	\mathbb{V}_{\theta_j}[g_j(x_j)] \\
	\leqslant&\alpha_0^2\sum_{j=1}^k\frac{j^{2\beta}}{k^{2\beta}}\frac{1}{j}
	\Big(M+M_V\|\nabla F(x_j)\|_2^2\Big) \\
	\leqslant&\alpha_0^2\Big(M+2M_V\|\nabla F(x_k)\|_2^2+2M_VL^2D^2\Big)\frac{1}{k^{2\beta}}\int_{1}^{k}j^{2\beta-1}\\
	\leqslant& \frac{\alpha_0^2}{2\beta}\Big(M+2M_V\|\nabla F(x_k)\|_2^2+2M_VL^2D^2\Big),
	\end{align*}
	and the proof is complete.
\end{proof}

\section{Experiments}
To compare the performance of the proposed method with that of other methods, we investigate different popular machine learning models, including logistic regression, multi-layer fully connected neural networks and deep convolutional neural networks. Experimental results show that our novel momentum term can efficiently solve practical stochastic optimization problems in the field of deep learning and outperforms other methods in deep convolutional neural networks.

In our experiments, we use the same parameter initialization strategy for different optimization algorithms. The values of hyper-parameters are selected, based on results, from the common used settings, respectively.

\subsection{Experiment: Logistic Regression}
We evaluate the two methods (saying Sgdm, and our method), on two multi-class logistic regression problems using the MNIST dataset without regularization. Logistic regression is suitable for comparing different optimizers for its simple structure and convex objective function. In our experiments, we set the stepsize $\alpha_t = \frac{\alpha}{\sqrt{t}}$, where $t$ is the current iteration times. The logistic regression problems is to classify the class label directly on the $28\times28$ image matrix.

\begin{figure}[htbp]
	\centering
	\subfigure[]{\includegraphics[width=2.55in]{log0.eps}}
		\label{fig1a}
	\subfigure[]{\includegraphics[width=2.55in]{log2.eps}}
		\label{fig1b}
	\caption{The negative log likelihood training cost of logistic regression on MNIST images. (a) Normal logistic regression. (b) Logistic regression after a two layer fully connected neural network.}
\end{figure}

We compare the performance of our method (Lim for short) to optimize the logistic regression problem with that of Sgdm using a minibatch size of 128. According to Fig. 1, we found that our method converges faster than Sgdm.

\subsection{Experiment: Multi-layer Fully Connected Neural Networks}
Multi-layer neural networks are powerful models with non-convex objective functions. We empirically found that our method outperforms Sgdm. In our experiments, the multi-layer neural network models are consistent with that in previous publications, saying a neural network model with two or three fully connected hidden layers with 1000 hidden units each and ReLU activation are used for this experiment with a minibatch size of 128.
\begin{figure}[htp]
	\centering
	\subfigure[]{\includegraphics[width=2.55in]{tfc1.eps}
		\label{fig9a}}
	\subfigure[]{\includegraphics[width=2.55in]{tfc2.eps}
		\label{fig9b}}
	\caption{Training cost of fully connected multilayer neural networks on MNIST images. (a) Neural network with two fully connected hidden layers.(b) Neural network with three fully connected hidden layers.}
	\label{fig9}
\end{figure}

We investigate the two optimizers using the standard deterministic cross-entropy objective function without regularization. According to Fig. 2, we found that our method  outperforms Sgdm by a large margin.

\subsection{Experiment: Deep Convolutional Neural Networks}
Deep convolutional neural networks (CNNs) have shown considerable success in practical machine learning tasks, e.g. computer vision tasks and natural language procession tasks. Our CNN architectures has three or two alternating stages of $5\times5$ convolution filters and $3\times3$ max pooling with stride of 2, each followed by a fully connected layer of 1000 units with RLeU activations. We pre-process the input image with whitening imply drop out noise to the input layer and fully connected layer. The minibatch size is also set to 128.

\begin{figure}[htp]
	\centering
	\subfigure[]{\includegraphics[width = 2.55in]{dc2n.eps}}
	\subfigure[]{\includegraphics[width = 2.55in]{dc3n.eps}}
	\label{fig3}
	\caption{Training cost of deep convolutional neural networks on MNIST images. (a) CNN with two convolutional layers.(b) CNN with three convolutional layers.}
\end{figure}

We investigate the three optimizers using the standard deterministic cross-entropy objective function. According to Fig. 3, we found that our method converge faster than Adam and Sgdm.

\section{Conclusion}
In this paper, we introduced a computationally efficient algorithm for gradient-based stochastic optimization problems. The updating strategies of the proposed method enjoys the simplicity of the original SGD with momentum but utilizes the momentum more efficiently than SGD with momentum. Our method is designed for machine learning problems with large scale data sets and non-convex optimization problems, where is hard for stochastic optimizers to achieve linear converge speed. The experiment results confirm our theoretical analysis on its convergence property and show that our method can solve practical optimization problems efficiently. Overall, we found that our method is a robust and well-suited method to a wide range of non-convex optimization problems in the field of machine learning.

\bibliography{acml20}

\end{document}


TITLE: Is taking the reciprocal of a differentiable strictly rigorous?
QUESTION [0 upvotes]: I've read a proof of $\frac{d}{dx}(\ln x)=\frac{1}{x}$ in which the reciprocal of $\frac{dx}{dy}$ is taken and was wondering if this is strictly rigorous. The proof was: $$y=\ln x$$ $$e^y=x$$ then take the derivative with respect to $y$, so $$e^y=\frac{dx}{dy}$$ then take the reciprocal of the differentiable to give $$\frac{1}{e^y}=\frac{dy}{dx}$$ and since $e^y=x$, $$\frac{dy}{dx}=\frac{1}{x}$$
the question is simply: is taking the reciprocal of a differentiable rigorous? I know considering it as a variable to add or subtract to different sides of an equation, but I (obviously) am not sure about this case. Any help is appreciated.

REPLY [2 votes]: This is a consequence of the chain rule.  For a function composition $F=f \circ g$, the rule states $$F'(x)=f'(g(x))g'(x)$$.  In other words, if you denote $y=g(x)$ and $z=f(y)$, then $$\frac{dz}{dx}=\frac{dz}{dy}\frac{dy}{dx}$$ Now if $g$ is an invertible function and $f$ is its inverse, then $$F=g^{-1}\circ g$$ is just the identity $F(x)=x$. In other words, $z=x$. Then $$\frac{dz}{dx}=1=\frac{dx}{dy}\frac{dy}{dx}$$ or
$$\frac{dx}{dy}=\frac{1}{\frac{dy}{dx}}$$ That's why you were okay to do it.


TITLE: Prove that $ab+a+b > 0$ if $a<-2$ and $b<-2$
QUESTION [0 upvotes]: I am interested in proving the following statement:

If $a<-2$ and $b <-2$ prove that $ab+a+b > 0$.

I tried using the fact that $ab>4$ and $a+b<-4$, but I couldn't progress any further, so this approach won't help me. Could I have a hint on how to start?

REPLY [5 votes]: Hint: $ab + a + b = (a+1)(b+1)-1$.

REPLY [1 votes]: Hint (mentioned in the comments by Martin R): Let $a=-2-u$ and $b=-2-v$, where $u$ and $v$ are positive numbers. Try substituting these values into the expression $ab+a+b$, and use the fact that $u$ and $v$ are positive to reach the desired conclusion.

This method is effectively the same as writing
\begin{align}
ab+a+b &= \overbrace{\bigl((a+2)-2\bigr)\bigl((b+2)-2\bigr)}^{=ab}+\overbrace{(a+2)+(b+2)-4}^{=a+b} \\[5pt]
&= (a+2)(b+2)-(a+2)-(b+2) \\[5pt]
&>0 \, .
\end{align}


text:
import algebra.homology.homology
import category_theory.abelian.homology

import for_mathlib.commsq
import for_mathlib.exact_lift_desc

/-!

# `has_homology f g H`

If `A B C H` are objects of an abelian category, if `f : A ⟶ B` and if `g : B ⟶ C`, then
a term of type `has_homology f g H` can be thought of as the claim that `H` "is" the
homology of the complex `A ⟶ B ⟶ C`, or, more precisely, as an isomorphism between `H`
and the homology of this complex.

-/

noncomputable theory

universes v u

open category_theory category_theory.limits

variables {𝓐 : Type u} [category.{v} 𝓐] [abelian 𝓐]
variables {A B C : 𝓐} {f : A ⟶ B} {g : B ⟶ C} {H : 𝓐}

/-- If `f : A ⟶ B` and `g : B ⟶ C` are morphisms in an abelian category, then `has_homology f g H`
is the claim that `f ≫ g = 0` and furthermore an identification of `H` with the middle homology of
the corresponding three term exact sequence formed by `f` and `g`. -/
structure has_homology (f : A ⟶ B) (g : B ⟶ C) (H : 𝓐) :=
(w : f ≫ g = 0)
(π : kernel g ⟶ H)
(ι : H ⟶ cokernel f)
(π_ι : π ≫ ι = kernel.ι _ ≫ cokernel.π _)
(ex_π : exact (kernel.lift g f w) π)
(ι_ex : exact ι (cokernel.desc f g w))
[epi_π : epi π]
[mono_ι : mono ι]

-- move me
instance (f : A ⟶ B) (g : B ⟶ C) (w : f ≫ g = 0) : epi (homology.π' f g w) := epi_comp _ _
-- move me
instance (f : A ⟶ B) (g : B ⟶ C) (w : f ≫ g = 0) : mono (homology.ι f g w) := mono_comp _ _

/-- If `f ≫ g = 0` then `homology f g w` can be identified with the homology of the three
term exact sequence coming from `f` and `g`. -/
def homology.has (f : A ⟶ B) (g : B ⟶ C) (w : f ≫ g = 0) :
  has_homology f g (homology f g w) :=
{ w := w,
  π := homology.π' f g w,
  ι := homology.ι f g w,
  π_ι := homology.π'_ι _ _ _,
  ex_π := begin
    delta homology.π',
    rw exact_comp_iso,
    exact abelian.exact_cokernel _
  end,
  ι_ex := begin
    delta homology.ι,
    rw exact_iso_comp,
    exact exact_kernel_ι
  end,
  epi_π := by apply_instance,
  mono_ι := by apply_instance }

lemma homology.has_π {f : A ⟶ B} {g : B ⟶ C} (w : f ≫ g = 0) :
  (homology.has f g w).π = homology.π' f g w := rfl

lemma homology.has_ι {f : A ⟶ B} {g : B ⟶ C} (w : f ≫ g = 0) :
  (homology.has f g w).ι = homology.ι f g w := rfl

namespace has_homology

attribute [instance] epi_π mono_ι
attribute [reassoc] π_ι

section misc

@[simp, reassoc] lemma ι_desc (hH : has_homology f g H) : hH.ι ≫ cokernel.desc f g hH.w = 0 :=
hH.ι_ex.w

@[simp, reassoc] lemma lift_π (hH : has_homology f g H) : kernel.lift g f hH.w ≫ hH.π = 0 :=
hH.ex_π.w

def of_iso {H₁ H₂ : 𝓐} (hH : has_homology f g H₁) (i : H₁ ≅ H₂) : has_homology f g H₂ :=
{ w := hH.w,
  π := hH.π ≫ i.hom,
  ι := i.inv ≫ hH.ι,
  π_ι := by simp [hH.π_ι],
  ex_π := exact_comp_iso.2 hH.ex_π,
  ι_ex := exact_iso_comp.2 hH.ι_ex,
  epi_π := epi_comp _ _,
  mono_ι := mono_comp _ _ }

end misc

section degenerate

-- move this; I couldn't find it
lemma exact_iso_comp_snd_iff_exact_comp_iso_fst_iff {D : 𝓐} (f : A ⟶ B) {e : B ⟶ C} (g : C ⟶ D)
  [is_iso e] : exact f (e ≫ g) ↔ exact (f ≫ e) g :=
⟨preadditive.exact_of_iso_of_exact' f (e ≫ g) (f ≫ e) g (iso.refl A) (as_iso e) (iso.refl D)
 (by simp) (by simp), preadditive.exact_of_iso_of_exact' (f ≫ e) g f (e ≫ g) (iso.refl A)
 (as_iso e).symm (iso.refl D) (by simp) (by simp)⟩

 -- move this; I couldn't find it
lemma exact_zero_right_of_epi [epi f] : exact f (0 : B ⟶ C) :=
⟨comp_zero, image_to_kernel_epi_of_epi_of_zero f⟩

local attribute [instance] epi_comp --`mono_comp` is a global instance!

def fst_eq_zero : has_homology (0 : A ⟶ B) g (kernel g) :=
{ w := zero_comp,
  π := 𝟙 _,
  ι := kernel.ι g ≫ cokernel.π 0,
  π_ι := by simp,
  ex_π := begin
    rw kernel.lift_zero,
    exact exact_zero_left_of_mono A,
  end,
  ι_ex := begin
    rw [← exact_iso_comp_snd_iff_exact_comp_iso_fst_iff, cokernel.π_desc],
    exact exact_kernel_ι,
  end,
  epi_π := infer_instance,
  mono_ι := infer_instance }

def snd_eq_zero : has_homology f (0 : B ⟶ C) (cokernel f) :=
{ w := comp_zero,
  π := kernel.ι 0 ≫ cokernel.π f,
  ι := 𝟙 _,
  π_ι := by simp,
  ex_π := begin
    rw [exact_iso_comp_snd_iff_exact_comp_iso_fst_iff, kernel.lift_ι],
    exact abelian.exact_cokernel f,
  end,
  ι_ex := begin
    rw [cokernel.desc_zero],
    exact exact_zero_right_of_epi,
  end,
  epi_π := infer_instance,
  mono_ι := infer_instance }

def snd_eq_zero' (hg : g = 0) : has_homology f g (cokernel f) :=
{ w := hg.symm ▸ comp_zero,
  π := kernel.ι g ≫ cokernel.π f,
  ι := 𝟙 _,
  π_ι := by simp,
  ex_π := begin
    subst hg,
    simp [exact_iso_comp_snd_iff_exact_comp_iso_fst_iff, kernel.lift_ι],
    exact abelian.exact_cokernel f,
  end,
  ι_ex := begin
    subst hg,
    rw [cokernel.desc_zero],
    exact exact_zero_right_of_epi,
  end,
  epi_π := by subst hg; apply_instance,
  mono_ι := infer_instance }

def fst_snd_eq_zero : has_homology (0 : A ⟶ B) (0 : B ⟶ C) B :=
{ w := comp_zero,
  π := kernel.ι 0,
  ι := cokernel.π 0,
  π_ι := rfl,
  ex_π := begin
    rw kernel.lift_zero,
    exact exact_zero_left_of_mono A,
  end,
  ι_ex := begin
    rw cokernel.desc_zero,
    exact exact_zero_right_of_epi,
  end,
  epi_π := infer_instance,
  mono_ι := infer_instance }

def fst_snd_eq_zero' (hf : f = 0) (hg : g = 0) : has_homology f g B :=
{ w := hf.symm ▸ zero_comp,
  π := kernel.ι g,
  ι := cokernel.π f,
  π_ι := rfl,
  ex_π := begin
    subst hf,
    rw kernel.lift_zero,
    exact exact_zero_left_of_mono A,
  end,
  ι_ex := begin
    subst hg,
    rw cokernel.desc_zero,
    exact exact_zero_right_of_epi,
  end,
  epi_π := by subst hg; apply_instance,
  mono_ι := by subst hf; apply_instance }

end degenerate

section ext

lemma ext_π (hH : has_homology f g H) {X : 𝓐} (φ ψ : H ⟶ X) (h : hH.π ≫ φ = hH.π ≫ ψ) : φ = ψ :=
by rwa cancel_epi at h

lemma ext_ι (hH : has_homology f g H) {X : 𝓐} (φ ψ : X ⟶ H) (h : φ ≫ hH.ι = ψ ≫ hH.ι) : φ = ψ :=
by rwa cancel_mono at h

end ext

section lift

variables (hH : has_homology f g H)
variables {X : 𝓐} (φ : X ⟶ cokernel f) (hφ : φ ≫ cokernel.desc f g hH.w = 0)

/-- If ``has_homology f g H` and `φ : X ⟶ cokernel f` composes to zero with the canonical
map `cokernel f ⟶ C` then `has_homology.lift φ` is the morphism `X ⟶ H` which recovers `φ` after
composing with the canonical map `H ⟶ cokernel f` (the statement that the triangle commutes
is `lift_comp_ι`). -/
def lift : X ⟶ H := hH.ι_ex.mono_lift φ hφ

@[simp, reassoc] lemma lift_comp_ι : hH.lift φ hφ ≫ hH.ι = φ := hH.ι_ex.mono_lift_comp φ hφ

lemma lift_unique (e : X ⟶ H) (he : e ≫ hH.ι = φ) : e = hH.lift φ hφ :=
hH.ι_ex.mono_lift_unique _ _ e he

@[simp] lemma lift_ι : hH.lift hH.ι hH.ι_desc = 𝟙 H :=
(hH.lift_unique _ _ _ $ category.id_comp _).symm

lemma π_eq_lift : hH.π = hH.lift (kernel.ι _ ≫ cokernel.π _)
  (by simp only [category.assoc, cokernel.π_desc, kernel.condition]) :=
lift_unique _ _ _ _ hH.π_ι

@[reassoc] lemma comp_lift {X Y : 𝓐} (φ : X ⟶ Y) (ψ : Y ⟶ cokernel f)
  (hψ : ψ ≫ cokernel.desc f g hH.w = 0) : φ ≫ hH.lift ψ hψ = hH.lift (φ ≫ ψ)
  (by rw [category.assoc, hψ, comp_zero]) :=
by { apply lift_unique, rw [category.assoc, lift_comp_ι] }

lemma homology_lift_eq {X Y Z W : 𝓐} (f : X ⟶ Y) (g : Y ⟶ Z) (w : f ≫ g = 0)
  (φ : W ⟶ cokernel f) (hφ) :
  homology.lift f g w φ hφ = (homology.has f g w).lift φ hφ :=
begin
  ext,
  simp only [homology.lift_ι],
  dsimp [has_homology.lift],
  erw [exact.mono_lift_comp],
end

end lift

section desc

variables (hH : has_homology f g H)
variables {X : 𝓐} (φ : kernel g ⟶ X) (hφ : kernel.lift g f hH.w ≫ φ = 0)

/-- If `has_homology f g H` and `φ : kernel g ⟶ X` becomes zero when precomposed with
the canonical map from `A` to `kernel g`, then `has_homology.desc φ` is the morphism `H ⟶ X` which
recovers `φ` after composing with the canonical map `kernel g ⟶ H`. The proof that this
triangle commutes is `π_comp_desc`. -/
def desc : H ⟶ X := hH.ex_π.epi_desc φ hφ

@[simp, reassoc] lemma π_comp_desc : hH.π ≫ hH.desc φ hφ = φ := hH.ex_π.comp_epi_desc φ hφ

lemma desc_unique (e : H ⟶ X) (he : hH.π ≫ e = φ) : e = hH.desc φ hφ :=
hH.ex_π.epi_desc_unique _ _ e he

@[simp] lemma desc_π : hH.desc hH.π hH.lift_π = 𝟙 H :=
(hH.desc_unique _ _ _ $ category.comp_id _).symm

lemma ι_eq_desc : hH.ι =
  hH.desc (kernel.ι _ ≫ cokernel.π _) (by simp only [kernel.lift_ι_assoc, cokernel.condition]) :=
desc_unique _ _ _ _ hH.π_ι

@[reassoc] lemma desc_comp {X Y : 𝓐} (φ : kernel g ⟶ X) (ψ : X ⟶ Y) (hφ : kernel.lift g f hH.w ≫ φ = 0) :
  hH.desc φ hφ ≫ ψ = hH.desc (φ ≫ ψ) (by rw [reassoc_of hφ, zero_comp]) :=
by { apply desc_unique, rw [π_comp_desc_assoc] }

lemma homology_desc_eq {X Y Z W : 𝓐} (f : X ⟶ Y) (g : Y ⟶ Z) (w)
  (φ : kernel g ⟶ W) (hφ) :
  homology.desc' f g w φ hφ = (homology.has f g w).desc φ hφ :=
begin
  ext,
  simp only [homology.π'_desc'],
  dsimp [has_homology.desc],
  simp only [exact.comp_epi_desc],
end

end desc

section map

variables {A₁ B₁ C₁ H₁ A₂ B₂ C₂ H₂ A₃ B₃ C₃ H₃ : 𝓐}
variables {f₁ : A₁ ⟶ B₁} {g₁ : B₁ ⟶ C₁} (h₁ : has_homology f₁ g₁ H₁)
variables {f₂ : A₂ ⟶ B₂} {g₂ : B₂ ⟶ C₂} (h₂ : has_homology f₂ g₂ H₂)
variables {f₃ : A₃ ⟶ B₃} {g₃ : B₃ ⟶ C₃} (h₃ : has_homology f₃ g₃ H₃)
variables {α : A₁ ⟶ A₂} {β : B₁ ⟶ B₂} {γ : C₁ ⟶ C₂}
variables {α' : A₂ ⟶ A₃} {β' : B₂ ⟶ B₃} {γ' : C₂ ⟶ C₃}
variables (sq1 : commsq f₁ α β f₂) (sq2 : commsq g₁ β γ g₂)
variables (sq1' : commsq f₂ α' β' f₃) (sq2' : commsq g₂ β' γ' g₃)

include h₁ h₂ sq1 sq2

/-- If `h₁ : has_homology f₁ g₁ H₁` and `h₂ : has_homology f₂ g₂ H₂` then given compatible morphisms
`f₁ ⟶ g₁` and `f₂ ⟶ g₂`, `has_homology.map h₁ h₂` is the induced morphism `H₁ ⟶ H₂`. -/
def map : H₁ ⟶ H₂ :=
h₁.desc (h₂.lift (kernel.ι _ ≫ β ≫ cokernel.π _) $
  by simp only [category.assoc, cokernel.π_desc, ← sq2.w, kernel.condition_assoc, zero_comp]) $
begin
  apply h₂.ext_ι,
  simp only [category.assoc, zero_comp, h₂.lift_comp_ι, kernel.lift_ι_assoc, sq1.w_assoc,
    cokernel.condition, comp_zero],
end

omit h₁ h₂ sq1 sq2

@[simp, reassoc] lemma π_map :
  h₁.π ≫ h₁.map h₂ sq1 sq2 = (h₂.lift (kernel.ι _ ≫ β ≫ cokernel.π _) $
  by simp only [category.assoc, cokernel.π_desc, ← sq2.w, kernel.condition_assoc, zero_comp]) :=
h₁.π_comp_desc _ _

@[simp, reassoc] lemma map_ι :
  h₁.map h₂ sq1 sq2 ≫ h₂.ι = (h₁.desc (kernel.ι _ ≫ β ≫ cokernel.π _) $
  by simp only [kernel.lift_ι_assoc, sq1.w_assoc, cokernel.condition, comp_zero]) :=
by { apply h₁.desc_unique, rw [h₁.π_map_assoc, h₂.lift_comp_ι] }

lemma π_map_ι : h₁.π ≫ h₁.map h₂ sq1 sq2 ≫ h₂.ι = kernel.ι _ ≫ β ≫ cokernel.π _ := by simp

lemma homology_map_eq (w₁ : f₁ ≫ g₁ = 0) (w₂ : f₂ ≫ g₂ = 0)
  (e₁ : α ≫ (arrow.mk f₂).hom = (arrow.mk f₁).hom ≫ β)
  (e₂ : β ≫ (arrow.mk g₂).hom = (arrow.mk g₁).hom ≫ γ) :
  homology.map w₁ w₂ (arrow.hom_mk e₁) (arrow.hom_mk e₂) rfl =
  (homology.has f₁ g₁ w₁).map (homology.has f₂ g₂ w₂)
  (commsq.of_eq e₁.symm) (commsq.of_eq e₂.symm) :=
begin
  --- I don't think using `exact.epi_desc` and `exact.mono_desc` is a good choice...
  rw homology.map_eq_desc'_lift_left,
  apply (homology.has _ _ w₁).ext_π,
  apply (homology.has _ _ w₂).ext_ι,
  simp [homology_lift_eq, homology_desc_eq],
end

lemma homology_map_eq' (w₁ : f₁ ≫ g₁ = 0) (w₂ : f₂ ≫ g₂ = 0) :
  homology.map w₁ w₂ ⟨α, β, sq1.w.symm⟩ ⟨β, γ, sq2.w.symm⟩ rfl =
  (homology.has f₁ g₁ w₁).map (homology.has f₂ g₂ w₂) sq1 sq2 :=
homology_map_eq _ _ _ _

lemma eq_map_of_π_map_ι (φ : H₁ ⟶ H₂) (hφ : h₁.π ≫ φ ≫ h₂.ι = kernel.ι g₁ ≫ β ≫ cokernel.π f₂) :
  φ = h₁.map h₂ sq1 sq2 :=
by rwa [← π_map_ι h₁ h₂ sq1 sq2, cancel_epi, cancel_mono] at hφ

@[simp, reassoc] lemma lift_map
  {X : 𝓐} (φ : X ⟶ cokernel f₁) (hφ : φ ≫ cokernel.desc f₁ g₁ h₁.w = 0) :
  h₁.lift φ hφ ≫ h₁.map h₂ sq1 sq2 = h₂.lift (φ ≫ cokernel.map f₁ f₂ α β sq1.w)
    (by { rw [category.assoc, cokernel.map_desc, reassoc_of hφ, zero_comp], exact sq2.w }) :=
begin
  apply lift_unique, rw [category.assoc, map_ι],
  conv_rhs { rw [← lift_comp_ι h₁ φ hφ, category.assoc] },
  congr' 1,
  apply h₁.ext_π,
  rw [π_comp_desc, π_ι_assoc, cokernel.π_desc],
end

-- move this
attribute [reassoc] limits.kernel.lift_map

@[simp, reassoc] lemma map_desc
  {X : 𝓐} (φ : kernel g₂ ⟶ X) (hφ : kernel.lift g₂ f₂ h₂.w ≫ φ = 0) :
  h₁.map h₂ sq1 sq2 ≫ h₂.desc φ hφ = h₁.desc (kernel.map g₁ g₂ β γ sq2.w ≫ φ)
    (by { rw [category_theory.limits.kernel.lift_map_assoc, hφ, comp_zero], exact sq1.w }) :=
begin
  apply desc_unique, rw [π_map_assoc],
  conv_rhs { rw [← π_comp_desc h₂ φ hφ, ← category.assoc] },
  congr' 1,
  apply h₂.ext_ι,
  rw [lift_comp_ι, category.assoc, π_ι, kernel.lift_ι_assoc, category.assoc],
end

/-- Gluing two commutative squares "vertically" (the convention is that `f`s and `g`s are
horizontal morphisms, and `α`s and `β`s are vertical morphisms). -/
def _root_.commsq.vcomp : commsq f₁ (α ≫ α') (β ≫ β') f₃ :=
commsq.of_eq $
calc f₁ ≫ β ≫ β' = α ≫ f₂ ≫ β'   : sq1.w_assoc β'
              ... = α ≫ α' ≫ f₃   : congr_arg _ $ sq1'.w
              ... = (α ≫ α') ≫ f₃ : (category.assoc _ _ _).symm

/-- A commutative square with identity isomorphisms for the two vertical maps. -/
def _root_.commsq.vrefl (f : A ⟶ B) : commsq f (iso.refl _).hom (iso.refl _).hom f :=
commsq.of_eq $ by rw [iso.refl_hom, iso.refl_hom, category.id_comp, category.comp_id]

/-- The reflection of a vertical square with isomorphisms for the vertical maps. -/
def _root_.commsq.vinv {α : A₁ ≅ A₂} {β : B₁ ≅ B₂} (sq1 : commsq f₁ α.hom β.hom f₂) :
  commsq f₂ α.inv β.inv f₁ :=
commsq.of_eq $ by rw [iso.comp_inv_eq, category.assoc, iso.eq_inv_comp, sq1.w]

lemma map_comp_map :
  h₁.map h₂ sq1 sq2 ≫ h₂.map h₃ sq1' sq2' = h₁.map h₃ (sq1.vcomp sq1') (sq2.vcomp sq2') :=
begin
  apply h₁.ext_π, apply h₃.ext_ι,
  simp only [category.assoc, map_ι, map_desc, π_comp_desc, kernel.lift_ι_assoc],
end

lemma map_id (h : has_homology f g H) {α : A ⟶ A} {β : B ⟶ B} {γ : C ⟶ C}
  (sq1 : commsq f α β f) (sq2 : commsq g β γ g) (hβ : β = 𝟙 _) :
  h.map h sq1 sq2 = 𝟙 H :=
begin
  apply h.ext_π, apply h.ext_ι,
  rw [π_map, lift_comp_ι, category.comp_id, π_ι, hβ, category.id_comp],
end

/- The isomorphism on `has_homology` induced by isomorphisms `f₁ ≅ f₂` and `g₁ ≅ g₂`. -/
@[simps] def map_iso {α : A₁ ≅ A₂} {β : B₁ ≅ B₂} {γ : C₁ ≅ C₂}
  (sq1 : commsq f₁ α.hom β.hom f₂) (sq2 : commsq g₁ β.hom γ.hom g₂) :
  H₁ ≅ H₂ :=
{ hom := h₁.map h₂ sq1 sq2,
  inv := h₂.map h₁ sq1.vinv sq2.vinv,
  hom_inv_id' := by { rw [map_comp_map, map_id], exact β.hom_inv_id },
  inv_hom_id' := by { rw [map_comp_map, map_id], exact β.inv_hom_id } }

/- The canonical isomorphism between H₁ and H₂ if both satisfy `has_homology f g Hᵢ`. -/
abbreviation iso (h₁ : has_homology f g H₁) (h₂ : has_homology f g H₂) :
  H₁ ≅ H₂ :=
map_iso h₁ h₂ (_root_.commsq.vrefl f) (_root_.commsq.vrefl g)

lemma iso_inv (h₁ : has_homology f g H₁) (h₂ : has_homology f g H₂) :
  (iso h₁ h₂).inv = (iso h₂ h₁).hom := rfl

lemma π_iso (h₁ : has_homology f g H₁) (h₂ : has_homology f g H₂) :
  h₁.π ≫ (h₁.iso h₂).hom = h₂.π :=
begin
  simp only [iso.refl_hom, category.id_comp, map_iso_hom, π_map],
  exact (π_eq_lift h₂).symm,
end

lemma iso_ι (h₁ : has_homology f g H₁) (h₂ : has_homology f g H₂) :
  (h₁.iso h₂).hom ≫ h₂.ι = h₁.ι :=
begin
  simp only [iso.refl_hom, category.id_comp, map_iso_hom, map_ι],
  exact (ι_eq_desc h₁).symm,
end

lemma map_iso_homology_map :
has_homology.map h₁ h₂ sq1 sq2 = (has_homology.iso h₁ (homology.has f₁ g₁ h₁.w)).hom ≫
  (homology.map h₁.w h₂.w ⟨α, β, sq1.w.symm⟩ ⟨β, γ, sq2.w.symm⟩ rfl) ≫
  (has_homology.iso h₂ (homology.has f₂ g₂ h₂.w)).inv:=
begin
  apply h₁.ext_π,
  apply h₂.ext_ι,
  simp [homology_map_eq'],
end

end map

section op

open opposite

def op (h : has_homology f g H) : has_homology g.op f.op (op H) :=
{ w := by rw [← op_comp, h.w, op_zero],
  π := (kernel_op_op f).hom ≫ h.ι.op,
  ι := h.π.op ≫ (cokernel_op_op g).inv,
  π_ι := by {
    simp only [kernel_op_op_hom, cokernel_op_op_inv, ← op_comp, category.assoc, h.π_ι_assoc,
      kernel.lift_ι_assoc, cokernel.π_desc], refl, },
  ex_π := begin
    rw [← exact_comp_hom_inv_comp_iff (kernel_op_op f), iso.inv_hom_id_assoc, kernel_op_op_hom],
    convert h.ι_ex.op using 1,
    apply quiver.hom.unop_inj,
    apply category_theory.limits.coequalizer.hom_ext,
    erw [unop_comp, coequalizer.π_desc_assoc, coequalizer.π_desc],
    rw [← unop_comp, kernel.lift_ι, g.unop_op],
  end,
  ι_ex := begin
    rw [← exact_comp_hom_inv_comp_iff (cokernel_op_op g), category.assoc, iso.inv_hom_id,
      category.comp_id, cokernel_op_op_inv],
    convert h.ex_π.op using 1,
    apply quiver.hom.unop_inj,
    apply category_theory.limits.equalizer.hom_ext,
    erw [unop_comp, equalizer.lift_ι, category.assoc, equalizer.lift_ι],
    rw [← unop_comp, cokernel.π_desc, f.unop_op],
  end,
  epi_π := epi_comp _ _,
  mono_ι := mono_comp _ _ }

-- @[simps]
def homology_unop_iso {A B C : 𝓐ᵒᵖ} (f : A ⟶ B) (g : B ⟶ C) (w : f ≫ g = 0) :
  homology f g w ≅ opposite.op (homology g.unop f.unop (by { rw [← unop_comp, w, unop_zero] })) :=
(homology.has f g w).iso (homology.has g.unop f.unop _).op

def homology_op_iso {A B C : 𝓐} (f : A ⟶ B) (g : B ⟶ C) (w : f ≫ g = 0) :
  homology g.op f.op (by rw [← op_comp, w, op_zero]) ≅ opposite.op (homology f g w) :=
homology_unop_iso _ _ _

end op

end has_homology

subset_name: curated