text:
\section{Introduction}

Bayesian models have proven to be one of the most successful classes of tools in machine learning. It stands out as a principled yet conceptually simple pipeline for combining expert knowledge and statistical evidence, modelling with complicated dependency structures and harnessing uncertainty by making probabilistic inferences \citep{geman1984stochastic,gelman2014bayesian}. In the past few decades, the Bayesian approach has been intensively used in modelling speeches \citep{rabiner1989tutorial}, text documents \citep{blei2003latent}, images/videos \citep{fei2005bayesian}, social networks \citep{airoldi2009mixed}, brain activity \citep{penny2011statistical}, and is often considered gold standard in many of these application domains. Learning a Bayesisan model typically involves sampling from a posterior distribution, therefore the learning process is inherently randomized.

Differential privacy (DP) is a cryptography-inspired notion of privacy \citep{dwork2006differential,dwork2006calibrating}. It is designed to provide a very strong form of protection of individual user's private information and at the same time allow data analyses to be conducted with proper utility. Any algorithm that preserves differential privacy must be appropriately randomized too. For instance, one can differential-privately release the average salary of Californian males by adding a Laplace noise proportional to the sensitivity of this figure upon small perturbation of the data sample.

In this paper, we connect the two seemingly unrelated concepts by showing that under standard assumptions, the intrinsic randomization in the Bayesian learning can be exploited to obtain a degree of differential privacy. In particular, we show that:
\begin{itemize}[itemsep=0mm]
\item   Any algorithm that produces a single sample from the exact (or approximate) posterior distribution of a Bayesian model with bounded log-likelihood is $\epsilon$ (or $(\epsilon,\delta)$)-differentially private\footnote{Similar observations were made in \citet{mir13} and \citet{dimitrakakis2014robust} under slightly different regimes and assumptions, and we will review them among other related work in Section~\ref{sec:relatedwork}.}. By the classic results in asymptotic statistics \citep{le1986bernstein,vandervaart2000asymptotic}, we show that this posterior sample is a consistent estimator whenever the Bayesian model is consistent; and near optimal whenever the asymptotic normality and efficiency of the maximum likelihood estimate holds.

\item The popular large-scale sampler Stochastic Gradient Langevin Dynamics~\citep{welling2011bayesian} and extensions, e.g. \citet{ahn2012bayesian,Chen2014SGHMC,ding2014bayesian} obey $(\epsilon,\delta)$-differentially private with no algorithmic changes when the stepsize is chosen to be small. This gives us a procedure that can potentially output many (correlated) samples from an approximate posterior distribution.
\end{itemize}

These simple yet interesting findings make it possible for differential privacy to be explicitly considered when designing Bayesian models, and for Bayesian posterior sampling to be used as a valid DP mechanism. We demonstrate empirically that these methods work as well as or better than the state-of-the-art differential private empirical risk minimization (ERM) solvers using objective perturbation~\citep{chaudhuri2011differentially, kifer2012private}.

The results presented in this paper are closely related to a number of previous work, e.g., \citet{mcsherry2007mechanism,mir13,bassily2014private,dimitrakakis2014robust}. Proper comparisons with them would require the knowledge of our results, thus we will defer detailed comparisons to Section~\ref{sec:relatedwork} near the end of the paper.

\section{Notations and Preliminary}

Throughout the paper, we assume data point $\boldsymbol  x\in \mathcal{X}$ and $\boldsymbol  \theta\in\Theta$ is the model. This can be the finite dimensional parameter of a single exponential family model or a collection of these in a graphical model, or a function in a Hilbert space or other infinite dimensional objects if the model is nonparametric. $\pi(\boldsymbol  \theta)$ denotes a prior blief of the model parameters and $p(\boldsymbol  x|\boldsymbol  \theta)$ and $\ell(\boldsymbol  x|\boldsymbol  \theta)$ are the likelihood and log-likelihood of observing data point $x$ given model parameter $\boldsymbol  \theta$. If we observe $X=\{\boldsymbol  x_1,...,\boldsymbol  x_n\}$, the posterior distribution
$$
\pi(\boldsymbol  \theta|X) = \frac{\pi(\boldsymbol  \theta)\prod_{i=1}^N p(\boldsymbol  x_i|\boldsymbol  \theta)}{\int \prod_{i=1}^N p(\boldsymbol  x_i|\boldsymbol  \theta) \pi(\boldsymbol  \theta) d\pi}
$$
denotes the updated belief conditioned on the observed data. Learning Bayesian models correspond to finding the mean or mode of the posterior distribution, but often, the entire distribution is treated as the output, which provides much richer information than just a point estimator. In particular, we get error bars of the estimators for free (credibility intervals).

Ignoring the philosophical disputes of Bayesian methods for the moment, practical challenges of Bayesian learning are often computational. As the models get more complicated, often there is not a closed-form expression for the posterior. Instead, we often rely on Markov Chain Monte Carlo methods, e.g., Metropolis-Hastings algorithm~\citep{hastings1970monte} to generate samples. This is often prohibitively expensive when the data is large. One recent approach to scale up Bayesian learning is to combine stochastic gradient estimation as in \citet{robbins1951stochastic} and Monte Carlo methods that simulates stochastic differential equations, e.g. \citet{neal2011mcmc}. These include Stochastic Gradient Langevin dynamics (SGLD) \citep{welling2011bayesian}, Stochstic Gradient Fisher scoring (SGFS) \citep{ahn2012bayesian}, Stochastic Gradient Hamiltonian Monte Carlo (SGHMC) \citep{Chen2014SGHMC} as well as more recent Stochastic Gradient Nos\'{e}-Hoover Thermostat (SGNHT) \citep{ding2014bayesian}. We will describe them with more details and show that these series of tools provide differential privacy as a byproduct of using stochastic gradient and requiring the solution to not collapse to a point estimate.

\subsection{Differential privacy}
Now we will talk about what we need to know about differential privacy. Let the space of data be $\mathcal{X}$ and data points $X,Y\in \mathcal{X}^n$.
Define $d(X,Y)$ to be the edit distance or Hamming distance between data set $X$ and $Y$, for instance, if $X$ and $Y$ are the same except one data point, then $d(X,Y)=1$.
\begin{definition}(Differential Privacy)
We call a randomized algorithm $\mathcal{A}$ $(\epsilon,\delta)$-differentially private with domain $\mathcal{X}^n$ if for all measurable set $S\subset \text{Range}(\mathcal{A})$ and for all $X,Y \in \mathcal{X}^{n}$ such that $d(X,Y)\leq 1$, we have
$$
\mathbb{P}(\mathcal{A}(X)\in S) \leq \exp(\epsilon) \mathbb{P}(\mathcal{A}(Y)\in S) + \delta.
$$
If $\delta=0$, then $\mathcal{A}$ is the called $\epsilon$-differential private.
\end{definition}
This definition naturally prevents linkage attacks and the identification of individual data from adversaries having arbitrary side information and infinite computational power. The promise of differential privacy has been interpreted in statistical testing, Byesian inference and information theory for which we refer readers to Chapter 1 of \citep{dwork2013algorithmic}.

There are several interesting properties of differential privacy that we will exploit here. Firstly, the definition is closed under postprocessing.
\begin{lemma}[Postprocessing immunity]\label{lemma:postprocessing}
If $\mathcal{A}$ is an $(\epsilon,\delta)$-DP algorithm, $\mathcal{B}\circ \mathcal{A}$ is also $(\epsilon,\delta)$-DP algorithm for any $\mathcal{B}$.
\end{lemma}
This is natural because otherwise the whole point of differential privacy will be forfeited. Also, the definition automatically allows for cases when the sensitive data are accessed more than once.
\begin{lemma}[Composition rule]\label{lemma:composition}
If algorithm $\mathcal{A}_1$ is $(\epsilon_1,\delta_1)$-DP, and $\mathcal{A}_2$ is $(\epsilon_2,\delta_2)$-DP then $(\mathcal{A}_1\otimes\mathcal{A}_2)$ is $(\epsilon_1+\epsilon_2,\delta_1+\delta_2)$-DP.
\end{lemma}
We will describe more advanced properties of DP as we need in Section~\ref{sec:sgld}.

\section{Posterior sampling and differential privacy}
In this section, we make a simple observation that under boundedness condition of a log-likelihood, getting one single sample from the posterior distribution (denoted by ``\textsc{OPS}  mechanism'' from here onwards) preserves a degree of differential privacy for free. Then we will cite classic results in statistics and show that this sample is a consistent estimator in a Frequentist sense and near-optimal in many cases.

\subsection{Implicitly Preserving Differential Privacy}

To begin with, we show that sampling from the posterior distribution is intrinsically differentially private.
\begin{theorem}\label{thm:private_posterior}
If $\sup_{\boldsymbol  x\in \mathcal{X},\boldsymbol  \theta\in\Theta}\left|\log p(\boldsymbol  x|\boldsymbol  \theta)\right| \leq B$, releasing one sample from the posterior distribution $p(\boldsymbol  \theta|X^n)$ with any prior preserves $4B$-differential privacy. Alternatively, if $\mathcal{X}$ is a bounded domain (e.g., $\|x\|_*\leq R \;\forall \boldsymbol  x\in \mathcal{X}$) and $\log p(\boldsymbol  x|\boldsymbol  \theta)$ is an $L$-Lipschitz function in $\|\cdot\|_*$ for any $\boldsymbol  \theta\in \Theta$, then releasing one sample from the posterior distribution preserves $4LR$-differential privacy.
\end{theorem}
\begin{proof}
The posterior distribution $p(\boldsymbol  \theta|\boldsymbol  x_1,...,\boldsymbol  x_n) = \frac{\prod_{i=1}^n p(\boldsymbol  x_i|\boldsymbol  \theta)p(\boldsymbol  \theta)}{\int_{\boldsymbol  \theta} \prod_{i=1}^n p(\boldsymbol  x_i|\boldsymbol  \theta)p(\boldsymbol  \theta) d\boldsymbol  \theta}$. For any $\boldsymbol  x_1,...,\boldsymbol  x_n, x'_k$,
The ratio can be factorized into
\begin{align*}
\frac{p(\boldsymbol  \theta|\boldsymbol  x_1,...,x'_k,...,\boldsymbol  x_n)}{p(\boldsymbol  \theta|\boldsymbol  x_1,...,\boldsymbol  x_k,...,\boldsymbol  x_n)} = \underbrace{\frac{p(\boldsymbol  x_k'|\boldsymbol  \theta)\prod_{i=1:n, i\neq k} p(\boldsymbol  x_i|\boldsymbol  \theta)p(\boldsymbol  \theta)}{\prod_{i=1}^n p(\boldsymbol  x_i|\boldsymbol  \theta)p(\boldsymbol  \theta)}}_\text{Factor 1}\times \underbrace{\frac{\int_{\boldsymbol  \theta} \prod_{i=1}^n p(\boldsymbol  x_i|\boldsymbol  \theta)p(\boldsymbol  \theta) d\boldsymbol  \theta}{ \int_{\boldsymbol  \theta} p(\boldsymbol  x_k'|\boldsymbol  \theta)\prod_{i=1:n, i\neq k} p(\boldsymbol  x_i|\boldsymbol  \theta)p(\boldsymbol  \theta)d\boldsymbol  \theta }}_\text{Factor 2}.
\end{align*}
\vspace{-2em}

It follows that
\begin{align*}
\text{Factor 1} &= \frac{p(\boldsymbol  x'_k|\boldsymbol  \theta)}{p(\boldsymbol  x_k|\boldsymbol  \theta)} = e^{\log p(\boldsymbol  x'_k|\boldsymbol  \theta) -\log p(\boldsymbol  x_k|\boldsymbol  \theta)} \leq e^{2B},\\
\text{Factor 2} &= \frac{\int_{\boldsymbol  \theta} \prod_{i\neq k} p(\boldsymbol  x_i|\boldsymbol  \theta)p(\boldsymbol  \theta) p(\boldsymbol  x_k)d\boldsymbol  \theta}{ \int_{\boldsymbol  \theta} p(\boldsymbol  x_k'|\boldsymbol  \theta)\prod_{i\neq k} p(\boldsymbol  x_i|\boldsymbol  \theta)p(\boldsymbol  \theta)d\boldsymbol  \theta }
= \frac{\int_{\boldsymbol  \theta} \prod_{i\neq k} p(\boldsymbol  x_i|\boldsymbol  \theta)p(\boldsymbol  \theta) p(\boldsymbol  x_k'|\boldsymbol  \theta) \frac{p(\boldsymbol  x_k)}{p(\boldsymbol  x_k')} d\boldsymbol  \theta}{ \int_{\boldsymbol  \theta} p(\boldsymbol  x_k'|\boldsymbol  \theta)\prod_{i\neq k} p(\boldsymbol  x_i|\boldsymbol  \theta)p(\boldsymbol  \theta)d\boldsymbol  \theta }\\
&= \frac{\int_{\boldsymbol  \theta} \prod_{i\neq k} p(\boldsymbol  x_i|\boldsymbol  \theta)p(\boldsymbol  \theta) p(\boldsymbol  x_k'|\boldsymbol  \theta) e^{\log p(\boldsymbol  x_k|\boldsymbol  \theta) - \log p(\boldsymbol  x_k'|\boldsymbol  \theta)} d\boldsymbol  \theta}{ \int_{\boldsymbol  \theta} p(\boldsymbol  x_k'|\boldsymbol  \theta)\prod_{i\neq k} p(\boldsymbol  x_i|\boldsymbol  \theta)p(\boldsymbol  \theta)d\boldsymbol  \theta }\\
&\leq e^{2B} \frac{m(\boldsymbol  x_1,...,\boldsymbol  x_k',...,\boldsymbol  x_n)}{m(\boldsymbol  x_1,...,\boldsymbol  x_k',...,\boldsymbol  x_n)} = e^{2B}.
\end{align*}
where we use $m(X)$ to denote the marginal distribution. As a result, the whole thing is bounded by $e^{4B}$.

Alternatively, we can use the Lipschitz constant and boundedness to get $\log p(\boldsymbol  x'_k|\boldsymbol  \theta) -\log p(\boldsymbol  x_k|\boldsymbol  \theta) \leq L\|x'_k-\boldsymbol  x_k\|_* \leq 2LR$.
\end{proof}

Readers familiar with differential privacy must have noticed that this is actually an instance of the exponential mechanism~\citep{mcsherry2007mechanism}, a general procedure that preserves privacy while making outputs with higher utility exponentially more likely. If one sets the utility function to be the log-likelihood and the privacy parameter being $4B$, then we get exactly the one-posterior sample mechanism.  This exponential mechanism point of view provides an an simple extension which allows us to specify $\epsilon$ by simply scaling the log-likelihood (see Algorithm~\ref{alg:OPS}). We will overload the notation \textsc{OPS}  to also represent this mechanism where we can specify $\epsilon$. The nice thing about this algorithm is that there is almost zero implementation effort to extend all posterior sampling-based Bayesian learning models to have differentially privacy of any specified $\epsilon$.

\begin{algorithm} [tb]
\caption{One-Posterior Sample (\textsc{OPS} ) estimator}
\label{alg:OPS}
\begin{algorithmic}
    \INPUT{ Data $X$, $\log$-likelihood function $\ell(\cdot|\cdot)$ satisfying $\sup_{\boldsymbol  x, \boldsymbol  \theta}\|\ell(\boldsymbol  x|\boldsymbol  \theta)\| \leq B$  a prior $\pi(\cdot)$. Privacy loss $\epsilon$.}
    \STATE{1.} Set $\rho= \min\{1,\frac{\epsilon}{4B}\}$.
    \STATE{2.} Re-define $\log$-likelihood function and the prior
    $\ell'(\cdot|\cdot) := \rho\ell(\cdot|\cdot)$ and $\pi'(\cdot) :=(\pi(\cdot) )^{\rho}.$
 \OUTPUT{ $\hat{ \boldsymbol  \theta} \sim P(\boldsymbol  \theta| X) \propto \exp\left(\sum_{i=1}^N \ell'(\boldsymbol  \theta|\boldsymbol  x_i)\right)\pi'(\boldsymbol  \theta)$.}
\end{algorithmic}
\end{algorithm}

\paragraph{Assumption on the boundedness.}
The boundedness on the loss-function (log-likelihood here) is a standard assumption in many DP works \citep{chaudhuri2011differentially,bassily2014private,song2013stochastic,kifer2012private}.
Lipschitz constant $L$ is usually small for continuous distributions (at least when the parameter space $\Theta$ is bounded). This is a bound on $\log p(\boldsymbol  x|\boldsymbol  \theta)$) so as long as $p(\boldsymbol  x|\boldsymbol  \theta)$ does not increase or decrease super exponentially fast at any point, $L$ will be a small constant. $R$ can also be made small by a simple preprocessing step that scales down all data points. In the aforementioned papers that assume $L$, it is typical that they also assume $R=1$ for convenience. So we will do the same. In practice, we can
algorithmically remove large data points from the data by some predefined threshold or using the ``Propose-Test-Release'' framework in \citep{dwork2009differential} or perform weighted training where we can assign lower weight to data points with large magnitude. Note that this is a desirable step for the robustness to outliers too. Exponential families (in Hilbert space) are an example, see e.g. \citet{bialek2001predictability,hofmann2008kernel,wainwright2008graphical}.

\subsection{Consistency and Near-Optimality}\label{sec:cons_nearoptimality}
Now we move on to study the consistency of the \textsc{OPS}  estimator. In great generality, we will show that the one-posterior sample estimator is consistent whenever the Bayesian model is posterior consistent. Since the consistency in Bayesian methods can have different meanings, we briefly describe two of them according to the nomenclature in \citet{orbanz2012lecture}.
\begin{definition}[Posterior consistency in the Bayesian Sense]\label{def:pos_cons1}
 For a prior $\pi$, we say the model is posterior consistent in the Bayesian sense,  if $\boldsymbol  \theta \sim \pi(\boldsymbol  \theta)$, $\boldsymbol  x_1,...,\boldsymbol  x_n \sim p_{\boldsymbol  \theta}$, and the posterior
 \vspace{-1em}
 $$\pi(\boldsymbol  \theta|\boldsymbol  x_1,...,\boldsymbol  x_n) \overset{\text{weakly}}{\longrightarrow} \delta_{\boldsymbol  \theta}  \text{ a.s. } \pi.$$
 $\delta_{\boldsymbol  \theta}$ is the dirac-delta function at $\boldsymbol  \theta$.
\end{definition}
In great generality, Doob's well-known theorem guarantees posterior consistency in the Bayesian sense for a model with any prior under no conditions except identifiability and measurability. A concise statement of Doob's result can be found in \citet[Theorem 10.10]{vandervaart2000asymptotic}).

An arguably more reasonable definition is given below. It applies to the case when the statistician who chooses the prior $\pi$ does not know about the true parameter.
\begin{definition}[Posterior consistency in the Frequentist Sense]\label{def:pos_cons2}
 For a prior $\pi$, we say the model is posterior consistent in the Frequentist sense,  if for every $\boldsymbol  \theta_0\in\Theta$, $\boldsymbol  x_1,...,\boldsymbol  x_n \sim p_{\boldsymbol  \theta}$, the posterior
 $$\pi(\boldsymbol  \theta|\boldsymbol  x_1,...,\boldsymbol  x_n) \overset{\text{weakly}}{\longrightarrow} \delta_{\boldsymbol  \theta_0}  \text{ a.s. }p_{\boldsymbol  \theta_0}. $$
\end{definition}
This type of consistency is much harder to satisfy especially when $\Theta$ is an infinite dimensional space, in which case the consistency often depends on the specific priors to use. A promising series of results on the consistency for Bayesian nonparametric models can be found in  \citet{ghosal2010dirichlet}).

Regardless which definition one favors, the key notion of consistency is that the posterior distribution to concentrates around the true underlying $\boldsymbol  \theta$ that generates the data.
\begin{proposition}
The one-posterior sample estimator is consistent \emph{if and only if} the Bayesian model is posterior consistent (in either Definition~\ref{def:pos_cons1}~or~\ref{def:pos_cons2} ).
\end{proposition}
\begin{proof}
The equivalence follows from the standard equivalence of convergence weakly and convergence in probability when a random variable converges weakly to a point mass.
\end{proof}

How about the rate of convergence? In the low dimensional setting when $\boldsymbol  \theta\in\Theta\subset \mathbb{R}^d$ and $p_{\boldsymbol  \theta}(\boldsymbol  x)$ is suitably differentiable and the prior is supported at the neighborhood of the true parameter, then by the Bernstein-von Mises theorem \citep{le1986bernstein}, the posterior mean is an asymptotically efficient estimator and the posterior distribution converges in $L_1$-distance to a normal distribution with covariance being the inverse Fisher Information.
\begin{proposition}\label{prop:efficiency}
Under the regularity conditions where Bernstein-von Mises theorem holds, the One-Posterior sample $\hat{\boldsymbol  \theta} \sim \pi(\boldsymbol  \theta|\boldsymbol  x_1,..,\boldsymbol  x_n) $ obeys
$$
\sqrt{n}(\hat{\boldsymbol  \theta} - \boldsymbol  \theta_0) \overset{\text{weakly}}{\longrightarrow}  \mathcal{N}(0, 2\mathbb{I}^{-1}),
$$
i.e., the One-Posterior sample estimator has an asymptotic relative efficiency of 2.
\end{proposition}
\begin{proof}
Let the One-Posterior sample $\hat{\boldsymbol  \theta} \sim \pi(\boldsymbol  \theta|\boldsymbol  x_1,..,\boldsymbol  x_n) $. By Bernstein-von Mises theorem
$
\sqrt{n}(\hat{\boldsymbol  \theta} - \tilde{\boldsymbol  \theta}) \overset{\text{weakly}}{\rightarrow}  \mathcal{N}(0, \mathbb{I}^{-1}).
$
By the asymptotical normality and efficiency of the posterior mean estimator  $\sqrt{n}(\tilde{\boldsymbol  \theta} -\boldsymbol  \theta_0) \overset{\text{weakly}}{\rightarrow}  \mathcal{N}(0, \mathbb{I}^{-1}).$
The proof is complete by taking the sum of the two asymptotically independent Gaussian vectors ($\tilde{\boldsymbol  \theta}$ and $\hat{\boldsymbol  \theta}-\tilde{\boldsymbol  \theta}$ are asymptotically independent).
\end{proof}
The above proposition suggests that in many interesting classes of parametric Bayesian models, the One-Posterior Sample estimator is asymptotically near optimal. Similar statements can also be obtained for some classes of semi-parametric and nonparametric Bayesian models \citep{ghosal2010dirichlet}, which we leave as future work

The drawback of the above two propositions is that they are only stated for the version of the OPS when $\epsilon=4B$. Using results in \citet{de2013bayesian} and \citet{kleijn2012bernstein} for Bayesian learning under misspecified models, we can prove consistency, asymptotic normality for any $\epsilon$ and parameterize the asymptotic relative efficiency of the \textsc{OPS}  estimator as a function of $\epsilon$. The key idea is that when scaling the log-likelihood and sample from a different distribution, we are essentially fitting a model that may not include the data-generating true distribution.  \citet{de2013bayesian} shows that under mild conditions, when the model is misspecified, the posterior distribution will converge to a point mass $\boldsymbol  \theta^*$ that minimizes the KL-divergence between between the true distribution and the corresponding distribution in the misspecified model. $\boldsymbol  \theta^*$ is essentially MLE and in our case, since we only scaled the distribution, the MLE will remain exactly the same. \citet{de2013bayesian}'s result is quite general and covers both parametric and nonparametric Bayesian models and whenever their assumptions hold, the \textsc{OPS}  estimator is consistent. Using a similar argument and the modifed Bernstein-Von-Mises theorem in \citet{kleijn2012bernstein}, we can prove asymptotic normality and near optimality for the subset of problems where regularities of MLE hold.
\begin{proposition}\label{prop:general_eps}
Under the same assumption as Proposition~\ref{prop:efficiency}, if we set a different $\epsilon$ by rescaling the log-likelihood by a factor of $\frac{\epsilon}{4B}$, then the the One-Posterior sample estimator obeys $$
\sqrt{n}(\hat{\boldsymbol  \theta} - \boldsymbol  \theta_0) \overset{\text{weakly}}{\longrightarrow}  \mathcal{N}\left(0, (1+\frac{4B}{\epsilon})\mathbb{I}^{-1}\right),
$$
in other word, the estimator has an ARE of $(1+\frac{4B}{\epsilon})$.
\end{proposition}
\begin{proof}
By scaling the log-likelihood, we are essentially changing the correct model $p_{\boldsymbol  \theta}$ to a misspecified model $(p_{\boldsymbol  \theta})^{\frac{\epsilon}{4B}}$. Let the true log-likelihood be $\ell$ and the misspecified log-likelihood be $\tilde{\ell} = \frac{\epsilon}{4B} \ell$, in addition, define
$$V(\boldsymbol  \theta) := \mathbb{E}_{\boldsymbol  \theta} \nabla\tilde{\ell}(\boldsymbol  \theta)\nabla\tilde{\ell}(\boldsymbol  \theta)^T = \frac{\epsilon^2}{16 B^2}\mathbb{E}_{\boldsymbol  \theta} \nabla\ell(\boldsymbol  \theta) \nabla\ell(\boldsymbol  \theta)^T = \frac{\epsilon^2}{16 B^2}\mathbb{I}(\boldsymbol  \theta)$$
$$J(\boldsymbol  \theta) :=  -\mathbb{E}_{\boldsymbol  \theta} \nabla^2\tilde{\ell}(\boldsymbol  \theta)= -\frac{\epsilon}{4 B}\mathbb{E}_{\boldsymbol  \theta} \nabla^2\ell(\boldsymbol  \theta) = -\frac{\epsilon}{4 B} \mathbb{I}(\boldsymbol  \theta).$$
The last equality holds under the standard regularity conditions. By the sandwich formula, the maximum likelihood estimator $\hat{\boldsymbol  \theta}$ under the misspecified model is asymptotically normal:
$$\sqrt{n}(\hat{\boldsymbol  \theta} - \boldsymbol  \theta^*) \overset{\text{weakly}}{\rightarrow} \mathcal{N}(0, J^{-1} V J(-1)) =\mathcal{N}(0, \mathbb{I}^{-1}) $$
where $\boldsymbol  \theta^*$ defines the closest (in terms of KL-divergence) model in the misspecified class of distributions to the true distribution that generates the data. Since the difference is only in scaling, the minimum KL-divergence is obtained at $\boldsymbol  \theta^* = \boldsymbol  \theta$. Now under the same regularity conditions, we can invoke the modified Bernstein-Von-Mises theorem for misspecified models \citep[Lemma~2.2]{kleijn2012bernstein}, which says that the posterior distribution $p(\theta|X^n)$ (of the misspecified model) converges in distribution to $\mathcal{N}(\hat{\boldsymbol  \theta}, (nJ)^{-1})$. In our case, $(nJ)^{-1} = \frac{4B}{n\epsilon}\mathbb{I}^{-1}$. The proof is concluded by noting that the posterior sample is an independent draw.
\end{proof}
We make a few interesting remarks about the result.
\begin{enumerate}
\item Proposition~\ref{prop:general_eps} suggests that for models with bounded log-likelihood, OPS is only a factor of $(1+4B/\epsilon)$ away from being optimal. This is in sharp contrast to most previous statistical analysis of DP methods that are only tight up to a numerical constant (and often a logarithmic term). In $\ell_2$-norm, the convergence rate is $O(\frac{\sqrt{1+4B/\epsilon}\|I^{-1}\|_F}{\sqrt{n}})$. The bound depends on the dimension through the Frobenius norm which is usually $O(\sqrt{d})$. The bound can be further sharpened using assumptions on the intrinsic rank, incoherence conditions or the rate of decays in eigenvalues of the Fisher information. In $\ell_\infty$-norm, the convergence rate is $\frac{\sqrt{1+4B/\epsilon}\|I^{-1}\|_2}{\sqrt{n}}$, which does not depend on the dimension of the problem.
\item Another implication is on statistical inference. Proposition~\ref{prop:general_eps} essentially generalizes that classic results in hypothesis testing and confidence intervals, e.g., Wald test, generalized likelihood ratio test, can be directly adopted for the private learning problems, with an appropriate calibration using $\epsilon$. We can control the type I error in an asymptotically exact fashion. In addition, the trade-off with $\epsilon$ and the test power is also explicitly described, so in cases where the power of the tests are well-studied \citep{lehmann2006testing}, the same handle can be used to analyze the most-powerful-test under privacy constraints.
\item Lastly, the results in \citet{de2013bayesian} and \citet{kleijn2012bernstein} are much more general. It is easy to extend the guarantee for \textsc{OPS}  to handle private Bayesian learning in a fully agnostic setting and in non-iid cases. We will leave the formalization of these claims as future directions.
\end{enumerate}

\subsection{(Efficient) sampling from approximate posterior}
The privacy guarantee in Theorem~\ref{thm:private_posterior} requires sampling from the exact posterior. In practice, however, exact samplers are rare. As Bayesian models get more and more complicated, often the only viable option is to use Markov Chain Monte Carlo (MCMC) samplers which are almost never exact. There are exceptions, e.g., \citet{propp1998coupling} but they only apply to problems with very special structures. A natural question to ask is whether we can still say something meaningful about privacy when the posterior sampling is approximate. It turns out that we can, and the level of approximation in privacy is the same as the level of approximation in the sampling distribution.
\begin{proposition}\label{prop:approx_sample}
If $\mathcal{A}$ that sampling from distribution $P_{X}$ preserves $\epsilon$-differential privacy, then any approximate sampling procedures $\mathcal{A}'$ that produces a sample from $P'_X$ such that $\|P_X-P'_X\|_{L_1}\leq \delta$ for any $X$ preserves $(\epsilon,(1+e^\epsilon)\delta)$-differential privacy.
\end{proposition}
\begin{proof}
For any $S\in \text{Range}(\mathcal{A}')$, and $d(X,X')\leq 1$
\begin{align*}
\mathbb{P}\left(\mathcal{A}'(X)\in S\right) &= \int_S dP'_X\leq \int_S dP_X +\delta\\
&\leq e^\epsilon \int_S  dP_{X'} +\delta \leq e^\epsilon \int_S  dP_{X'} \\
&\leq e^\epsilon \int_S  dP'_{X'} + (1+e^\epsilon)\delta\\
&=e^\epsilon \mathbb{P}\left(\mathcal{A}'(X')\in S\right) + (1+e^\epsilon)\delta,
\end{align*}
This is $(\epsilon,(1+e^\epsilon)\delta)$-DP by definition.
\end{proof}
We are using $L_1$ distance of the distribution because it is a commonly accepted metric to measure the convergence rate MCMC \cite{rosenthal1995minorization}, and Proposition~\ref{prop:approx_sample} leaves a clean interface for computational analysis in determining the number of iterations needed to attain a specific level of privacy protection.

\paragraph{A note on computational efficiency.}
The (unsurprising) bad news is that even approximate sampling from the posterior is NP-Hard in general, see, e.g. \citet[Theorem~8]{sontag2011complexity}. There are however interesting results on when we can (approximately) sample efficiently. Approximation is easy for sampling LDA when $\alpha>1$ while NP-Hard when $\alpha<1$.  A more general result in \citet{applegate1991sampling} suggests that we can get a sample with arbitrarily close approximation in polynomial time for a class of near log-concave distributions. The log-concavity of the distributions would imply convexity in the log-likelihood, thus, this essentially confirms the computational efficiency of all convex empirical risk minimization problems under differential privacy constraint (see \citet{bassily2014private}).

The nice thing is that since we do not modify the form of the sampling algorithm at all, the \textsc{OPS}  algorithm is going to be a computationally tractable DP method whenever the Bayesian learning model of interest is proven to be computationally tractable.

This observation provides an interesting insight into the problem of computational lower bound of differential private machine learning. Unlike what is conjectured in \citet{dwork2014preserving}, our observation seems to suggest that the computational barrier is not specific to differential privacy, but rather the barrier of learning in general. The argument seems to hold at least for some class of problems, where the posterior sample achieves the optimal statistical rate and is at least $4B$-DP.

\subsection{Discussions and comparisons}
 \textsc{OPS}   has a number of advantages over the state-of-the-art differentially private ERM method: objective perturbation \citep{chaudhuri2011differentially,kifer2012private} (\textsc{ObjPert}  from here onwards). \textsc{OPS}  works with arbitrary bounded loss functions and priors while \textsc{ObjPert}  needs a number of restrictive assumptions including twice differentiable loss functions, strongly convexity parameter to be greater than a threshold and so on. These restrictions rule out many commonly used loss functions, e.g., $\ell_1$-loss, hinge loss, Huber function just to name a few.

 Also, \textsc{ObjPert} 's privacy guarantee holds only for the exact optimal solution, which is often hard to get in practice. In contrast, \textsc{OPS}  works when the sample is drawn from an approximate posterior distribution. From a practical point of view, since \textsc{OPS}  stems from the intrinsic privacy protection of Bayesian learning, it requires very little implementation effort to deploy it for practical applications. It also requires the problem to be strong convexity with a minimum strong convexity parameter. When the condition is not satisfied, \textsc{ObjPert}  will need to add additional quadratic regularization to make it so, which may bias the problem unnecessarily.

\section{Stochastic Gradient MCMC and $(\epsilon,\delta)$-Differential privacy}\label{sec:sgld}
Given a fixed privacy budget, we see that the single posterior sample produces an optimal point estimate, but what if we want multiple samples? Can we use the privacy budget in a different way that produces many approximate posterior samples?

 In this section we will provide an answer to it by looking at a class of Stochastic Gradient MCMC techniques developped over the past few years. We will show that they are also differentially private for free if the parameters are chosen appropriately.

The idea is to simply privately release an estimate of the gradient (as in \citet{song2013stochastic,bassily2014private}) and leverage upon the following two celebrated lemmas in differential privacy in the same way as \citet{bassily2014private} does in deriving the near-optimal $(\epsilon,\delta)$-differentially private SGD.

The first lemma is the advanced composition which allows us to trade off a small amount of $\delta$ to get a much better bound for the privacy loss due to composition.
\begin{lemma}[Advanced composition, c.f.,Theorem 3.20 in \citep{dwork2013algorithmic}]\label{lemma:adv_composition}
For all $\epsilon,\delta,\delta'\geq 0$, the class of $(\epsilon,\delta)$-DP mechanisms satisfy $(\epsilon',k\delta+\delta')$-DP under $k$-fold adaptive composition for:
$$
\epsilon'=\sqrt{2k\log(1/\delta')} \epsilon + k \epsilon(e^{\epsilon}-1).
$$
\end{lemma}
\begin{remark}\label{rmk:adv_composition}
When $\epsilon = \frac{c}{\sqrt{2k\log(1/\delta')}}<1$ for some constant $c<\sqrt{\log(1/\delta')}$, we can simplify the above expression into
$
\epsilon' \leq  2c.
$
To see this, apply the inequality $e^{\epsilon}-1\leq 2\epsilon$ (easily shown via Taylor's theorem and the assumption that $\epsilon\leq 1$)
\end{remark}
In addition, we will also make use of the following lemma due to \citet{beimel2014bounds}.
\begin{lemma}[Privacy for subsampled data. Lemma~4.4 in \citet{beimel2014bounds}.]\label{lemma:subsampling}
Over a domain of data sets $\mathcal{X}^N$, if an algorithm $\mathcal{A}$ is $(\epsilon,\delta)$ differentially private (with $\epsilon<1$), then for any data set $X\in \mathcal{X}^N$, running $\mathcal{A}$ on a uniform random $\gamma N$-entries of $X$ ensures $(2\gamma \epsilon,\delta)$-DP.
\end{lemma}

To make sense of the above lemma, notice that we are subsampling uniform randomly and the probability of any single data point being sampled is only $\gamma$. Thus, if we arbitrarily perturb one of the data points, its impact is evenly spread across all data points thanks to random sampling.

Let $f: \mathcal{X}^n \rightarrow \mathbb{R}^d$ be an arbitrary $d$-dimensional function. Define the $\ell_2$ sensitivity of $f$ to be
$$\Delta_2 f= \sup_{Y: d(X,Y)\leq 1} \|f(X)-f(Y)\|_2.$$
Suppose we want to output $f(X)$ differential privately, ``Gaussian Mechanism'' output $\hat{f}(X) = f(X) + \mathcal{N}(0,\sigma^2 I_d)$ for some appropriate $\sigma$.
\begin{theorem}[Gaussian Mechanism, c.f. \citet{dwork2013algorithmic}]\label{lemma:gauss_mech}
Let $\epsilon\in(0,1)$ be arbitrary. ``Gaussian Mechanism'' with $\sigma \geq \Delta_2 f \sqrt{2\log(1.25/\delta)}/\epsilon$ is $(\epsilon,\delta)$-differentially private.
\end{theorem}
This will be the main workhorse that we use here.

\subsection{Stochastic Gradient Langevin Dynamics}

SGLD iteratively update the parameters to by running a perturbed version of the minibatch stochastic gradient descent on the negative log-posterior objective function
$$
 - \sum_{i=1}^{N}\log p(\boldsymbol  x_i|\boldsymbol  \theta) -\log \pi(\boldsymbol  \theta)=: \sum_{i=1}^{N}\ell(\boldsymbol  x_i;\boldsymbol  \theta) + r(\boldsymbol  \theta)
$$
where $\ell(\boldsymbol  x_i;\boldsymbol  \theta)$ and $r(\boldsymbol  \theta)$ are loss-function and regularizer under the empirical risk minimization.

If one were to run stochastic gradient descent or any other optimization tools on this, one would eventually a deterministic maximum a posteriori estimator. SGLD avoids this by adding noise in every iteration.
At iteration $t$ SGLD first samples uniform randomly $\tau$ data points $\{\boldsymbol  x_{t_1},...,\boldsymbol  x_{t_2}\}$ and then updates the parameter using
\begin{equation}\label{eq:SGLD}
\boldsymbol  \theta_{t+1} = \boldsymbol  \theta_t - \eta_t\left(\nabla r(\boldsymbol  \theta) +\frac{N}{\tau}\sum_{i=1}^\tau\nabla \ell(\boldsymbol  x_{ti}|\boldsymbol  \theta)\right) + \boldsymbol  z_t,
\end{equation}
where $\boldsymbol  z_t\sim \mathcal{N}(0,\eta_t)$ and $\tau$ is the mini-batch size.

For the ordinary stochastic gradient descent to converge in expectation, the stepsize $\eta_t$ can be chosen as anything that $\sum_{i=1}^{\infty} \eta_t= \infty$ and $\sum_{i=1}^{\infty} \eta_t^2 <\infty$ \citep{robbins1951stochastic}. Typically, one can chooses stepsize $\eta_t = a(b+t)^{-\gamma}$ with $\gamma\in(0.5,1]$. In fact, it is shown that for general convex functions and $\mu$-strongly convex functions $\frac{1}{\sqrt{t}}$ and $\frac{1}{\mu t}$ can be used to obtain the minimax optimal $O(1/\sqrt{t})$ and $O(1/t)$ rate of convergence. These results substantiate the first phase of SGLD: a convergent algorithm to the optimal solution. Once it gets closer, however, it transforms into a posterior sampler. According to \citet{welling2011bayesian} and later formally proven in \citet{sato2014approximation}, if we choose $\eta_t \rightarrow 0 $, the random iterates $\boldsymbol  \theta_t$ of SGLD converges in distribution to the $p(\boldsymbol  \theta|X)$. The idea is that as the stepsize gets smaller, the stochastic error from the true gradient due to the random sampling of the minibatch converges to $0$ faster than the injected Gaussian noise.

In addition, if we use some fixed stepsize lower bound, such that $\eta_t = \max\{1/(t+1),\eta_0\}$ (to alleviate the slow mixing problem of SGLD), the results correspond to a discretization approximation of a stochastic differential equation (Fokker-Planck equation), which obeys the following theorem due to \citet{sato2014approximation} (simplified and translated to our notation).
\begin{theorem}[Weak convergence \citep{sato2014approximation}]
Assume $f(\boldsymbol  \theta|X)$ is differentiable, $\nabla f(\boldsymbol  \theta |X)$ is gradient Lipschitz and bounded \footnote{We use boundedness to make the presentation simpler. Boundedness trivially implies the linear growth condition in \citet[Assumption 2]{sato2014approximation}.}. Then
$$\left|\mathbb{E}_{\boldsymbol  \theta\sim p(\boldsymbol  \theta|X)}[h(\boldsymbol  \theta)] - \mathbb{E}_{\boldsymbol  \theta \sim SGLD}[h(\boldsymbol  \theta(t))]\right| = O(\eta_t),$$
for any continuous and polynomial growth function $h$.
\end{theorem}
This theorem implies that one can approximate the posterior mean (and other estimators) using SGLD. Finite sample properties of SGLD is also studied in \citep{vollmer2015non}.

Now we will show that with a minor modification to just the ``burn-in'' phase of SGLD, we will be able to make it differentially private (see Algorithm~\ref{alg:DP-SGLD}).

\begin{algorithm}[b]
\caption{Differentially Private Stochastic Gradient Langevin Dynamics (DP-SGLD)}
\label{alg:DP-SGLD}
\begin{algorithmic}
    \REQUIRE Data $X$ of size $N$, Size of minibatch $\tau$, number of data passes $T$, privacy parameter $\epsilon,\delta$, Lipschitz constant $L$ and  initial $\boldsymbol  \theta_1$. Set $t=1$.
	\FOR{$t=1:\lfloor NT/\tau\rfloor$}
	   \STATE{1.} Random sample a minibatch $S\subset [N]$ of size $\tau$.
 	   \STATE{2.} Sample each coordinate of $\boldsymbol  z_t$ iid from
 	   $ \mathcal{N}\left( 0, \frac{128NT L^2}{ \tau\epsilon^2}\log\Big(\frac{2.5NT}{\tau\delta}\Big)\log(2/\delta)  \eta_t^2 \vee  \eta_t\right).$
 	   \STATE{3.} Update $\boldsymbol  \theta_{t+1}\leftarrow \boldsymbol  \theta_t - \eta_t\left(\nabla r(\boldsymbol  \theta) +\frac{N}{\tau}\sum_{i\in S}\nabla \ell(\boldsymbol  x_{i}|\boldsymbol  \theta)\right) + \boldsymbol  z_t,$
        \STATE{4.} Return $\boldsymbol  \theta_{t+1}$ as a posterior sample (after a pre-defined burn-in period).
 	   \STATE{5.} Increment $t\leftarrow t+1.$
    \ENDFOR
\end{algorithmic}
\end{algorithm}
\begin{algorithm}[b]
\caption{Hybrid Posterior Sampling Algorithm}
\label{alg:hybrid}
\begin{algorithmic}
    \REQUIRE Data $X$ of size $N$, $\log$-likelihood function $\ell(\cdot|\theta)$ with Lipschitz constant $L$ in the first argument, assume $\sup_{\boldsymbol  x\in\mathcal{X}}\|\boldsymbol  x\|$, a prior $\pi$. Privacy requirement $\epsilon$.
    \STATE{1. } Run OPS estimator: Algorithm~\ref{alg:OPS} with $\epsilon/2$. Collect sample point $\theta_0$
    \STATE{2. } Run DP-SGLD (Algorithm~\ref{alg:DP-SGLD}) or other Stochatic Gradient Monte Carlo algorithms and collect samples.
 	\OUTPUT: Return all samples.
\end{algorithmic}
\end{algorithm}

\begin{theorem}[Differentially private Minibatch SGLD]\label{thm:private_SGLD}
Assume initial $\boldsymbol  \theta_1$ is chosen independent of the data, also assume $\ell(\boldsymbol  x|\boldsymbol  \theta)$ is $L$-smooth in $\|\cdot \|_2$ for any $\boldsymbol  x\in \mathcal{X}$ and $\boldsymbol  \theta\in \Theta$. In addition, let $\epsilon,\delta, \tau, T$ be chosen such that $T\geq \frac{\epsilon^2 N}{32\tau \log(2/\delta)}$.
Then Algorithm~\ref{alg:DP-SGLD} preserves $(\epsilon,\delta)$-differential privacy.
\end{theorem}
\begin{proof}
In every iteration, the only data access is $\sum_{i\in S}\nabla \ell(\boldsymbol  x_{i}|\boldsymbol  \theta)$  and by the $L$-Lipschitz condition, the sensitivity of $\sum_{i\in S}\nabla \ell(\boldsymbol  x_{i}|\boldsymbol  \theta)$ is at most $2L$. Get the essential noise that is added to $\sum_{i\in S}\nabla \ell(\boldsymbol  x_{i}|\boldsymbol  \theta)$ by removing the $\frac{N^2\eta_t^2}{\tau^2}$ factor from the variance $\sigma^2$ in the algorithm, and Gaussian mechanism, ensures the privacy loss to be smaller than $\frac{\epsilon\sqrt{N}}{\sqrt{32\tau T\log (2/\delta)}}$ with probability $>1-\frac{\tau\delta}{2NT}$.

Using the same technique in \citet{bassily2014private}, we can further exploit the fact that the subset $S$ that we use to compute the stochastic gradient is chosen uniformly randomly. By Lemma~\ref{lemma:subsampling}, the privacy loss for this iteration is in fact
$$\frac{\epsilon\sqrt{N}}{\sqrt{32\tau T\log (2/\delta)}} \cdot \frac{2\tau}{N} = \frac{\epsilon/2}{\sqrt{2(NT/\tau) \log(2/\delta)}}.$$
Verify that we can indeed do that as $\frac{\epsilon\sqrt{N}}{\sqrt{32\tau T\log (2/\delta)}} <1$ from the assumption on $T$. Note that to get $T$ data passes with minibatches of size $\tau$, we need to go through at most $\lfloor \frac{NT}{\tau}\rfloor\leq \frac{NT}{\tau}$ iterations. Apply the advanced composition theorem (Remark~\ref{rmk:adv_composition}), we get an upper bound of the total privacy loss $\epsilon$ and  failure probability $\delta = \frac{\delta}{2} + \frac{\tau\delta}{2NT} \cdot \frac{NT}{\tau}$ accordingly.

The proof is complete by noting that choosing a larger noise level when $\eta_t$ is bigger can only reduces the privacy loss under the same failure probability.
\end{proof}

\paragraph{$\alpha$-Phase transition.} For any $\alpha\in (0,1)$, if we choose $\eta_t = \frac{\alpha \epsilon^2}{128L^2\log(2.5NT/(\tau\delta))\log(2/\delta) t}$, then whenever $t>\alpha NT/\tau$, then we are essentially running SGLD for the last $(1-\alpha)NT/\tau$ iterations, and we can collect approximate posterior samples from there.

\paragraph{Small constant $\eta_0$.}
Instead of making $\eta_t$ to converge to $0$ as $t$ increases, we may alternatively use constant $\eta_0$ after $t$ is larger than a threshold. This is a suggested heuristic in \citet{welling2011bayesian} and is inline with the analysis in \citet{sato2014approximation} and \citet{vollmer2015non}.

\paragraph{Choice of $T$ and $\tau$}
By \citet{bassily2014private}, it takes at least $N$ data passes to converge in expectation to a point near the minimizer, so taking $T=2N$ is a good choice.
 The variance of both random components in our stochastic gradient is smaller when we use larger $\tau$. Smaller variances would improve the convergence of the stochastic gradient methods and make the SGLD a better approximation to the full Langevin Dynamics. The trade-off is that  when $\tau$ is too large, we will use up the allowable $T$ datapasses with just $O(T)$ iterations and the number of posterior samples we collect from the algorithm will be small.

\paragraph{Overcoming the large-noise in the ``Burn-in'' phase}
When the stepsize $\eta_t$ is not small enough initially, we need to inject significantly more noise than what SGLD would have to ensure privacy. We can overcome this problem by initializing the SGLD sampler with a valid output of the \textsc{OPS}  estimator, modified according to the exponential mechanism so that the privacy loss is calibrated to $\epsilon/2$. As the initial point is already in the high probability region of the posterior distribution, we no longer need to ``Burn-in'' the Monte Carlo sampler so we can simply choose a sufficiently small constant stepsize so that it remains a valid SGLD. This algorithm is summarized in Algorithm~\ref{alg:hybrid}.

\paragraph{Comparing to \textsc{OPS} }
The privacy claim of DP-SGLD is very different from \textsc{OPS} . It does not require sampling to be nearly correct to ensure differential privacy. In fact, DP-SGLD privately releases the entire sequence of parameter updates, thus ensures differential privacy even if the internal state of the algorithm gets hacked. However, the quality of the samples is usually worse than \textsc{OPS}  due to the random-walk like behavior. The interesting fact, however, is that if we run SGLD indefinitely without worrying about the stronger notion of internal privacy, it leads to a valid posterior sample. We can potentially modify the posterior distribution to sample from into the ``scaled'' version so as to balancing the two ways of getting privacy.

\subsection{Hamiltonian Dynamics, Fisher Scoring and Nose-Hoover Thermostat}
One of the practical drawback of SGLD is its random walk-like behavior which slows down the mixing significantly. In this section, we describe three extensions of SGLD that attempts to resolve the issue by either using auxiliary variables to counter the noise in the stochastic gradient\citep{Chen2014SGHMC,ding2014bayesian}, or to exploit second order information so as to use Newton-like updates with large stepsize \citep{ahn2012bayesian}.

We note that in all these methods, stochastic gradients are the only form of data access, therefore similar results like what we described for SGLD follow nicely. We briefly describe each method and how to choose their parameters for differential privacy.

\paragraph{Stochastic Gradient Hamiltonian Monte Carlo.}
 According to \citet{neal2011mcmc}, Langevin Dynamics is a special limiting case of Hamiltonian Dynamics, where one can simply ignore the ``momentum'' auxiliary variable.  In its more general form, Hamiltonian Monte Carlo (HMC) is able to generate proposals from distant states and hence enabling more rapid exploration of the state space.
\citet{Chen2014SGHMC} extends the full ``leap-frog'' method for HMC in \citet{neal2011mcmc} to work with stochastic gradient and add a ``friction'' term in the dynamics to ``de-bias'' the noise in the stochastic gradient.
\begin{equation}\label{eq:SGHMC}
  \left\{
    \begin{array}{ll}
      \boldsymbol  \theta_t = \boldsymbol  \theta_{t-1} + h_t  \boldsymbol  r_{t-1}\\
      \boldsymbol  p_t = \boldsymbol  p_{t-1} - h_t \widehat{\nabla} -\eta_t A \boldsymbol  p_{t-1} + \mathcal{N}(0, 2(A-\widehat{B}) h_t).
    \end{array}
  \right.
\end{equation}
where $\widehat{B}$ is a guessed covariance of the stochastic gradient (the authors recommend  restricting $\hat{B}$ to a single number or a diagonal matrix) and
$A$ can be arbitrarily chosen as long as $A\succ \widehat{B}$. If the stochastic gradient $\widehat{\nabla}\sim \mathcal{N}(\nabla, B)$ for some $B$ and $\widehat{B}=B$, then this dynamics is simulating a dynamic system that yields the correct distribution. Note that even if the normal assumption holds and we somehow set $\widehat{B}=B$, we still requires $h_t$ to go to $0$ to sample from the actual posterior distribution, and as $h_t$ converges to $0$ the additional noise we artificially inject dominates and we get privacy for free. All we need to do is to set $A$, $\widehat{B}$ and $h_t$ so that
$2(A-\widehat{B}) /h_t\succ \frac{128NT L^2}{ \tau\epsilon^2}\log\Big(\frac{2.5NT}{\tau\delta}\Big)\log(2/\delta)  I_n$.
Note that as $h_t\rightarrow 0$ this quickly becomes true.

\paragraph{Stochastic Gradient Nos\'{e}-Hoover Thermostat}
As we discussed, the key issue about SGHMC is still in choosing $\widehat{B}$. Unless $\widehat{B}$ is chosen exactly as the covariance of true stochastic gradient, it does not sample from the correct distribution even as $h_t\rightarrow 0$ unless we trivially set $\hat{B}=0$. The Stochastic Gradient Nos\'{e}-Hoover Thermostat (SGNHT) overcomes the issue by introducing an additional auxiliary variable $\xi$, which serves as a thermostat to absorb the unknown noise in the stochastic gradient. The update equations of SGNHT are given below
\begin{equation}\label{eq:SGNHT}
  \left\{
    \begin{array}{ll}
      \boldsymbol  p_t = \boldsymbol  p_{t-1} - \xi_{t-1}\boldsymbol  p_{t-1}h_t - \widehat{\nabla}h_t + \mathcal{N}(0, 2Ah_t);\\
      \boldsymbol  \theta_t = \boldsymbol  \theta_{t-1} + h_t \boldsymbol  p_{t-1};\\
      \xi_t = \xi_{t-1} + (\frac{1}{n} \boldsymbol  p_t^T\boldsymbol  p_t -1) h_t.
    \end{array}
  \right.
\end{equation}
Similar to the case in SGHMC, appropriately selected discretization parameter $h_t$ and the friction term $A$ will imply differential privacy.

\citet{Chen2014SGHMC,ding2014bayesian} both described a reformulation that can be interpret as SGD with momentum. This is by setting parameters  $\eta=h^2, a=hA, \hat{b}=h \widehat B$ for SGHMC:
\begin{equation}\label{eq:SGHMC_reform}
  \left\{
    \begin{array}{ll}
      \boldsymbol  \theta_t = \boldsymbol  \theta_{t-1} + \boldsymbol  v_{t-1}\\
      \boldsymbol  v_t = \boldsymbol  v_{t-1} - \eta_t \widehat{\nabla} - a\boldsymbol  v + \mathcal{N}(0, 2(a-\widehat{b}) \eta_tI);
    \end{array}
  \right.
\end{equation}
and $\boldsymbol  v = \boldsymbol  p h, \eta_t=h_t^2,\alpha=\xi h$ and $a = Ah$ for SGNHT:
\begin{equation}\label{eq:SGNHT_reform}
  \left\{
    \begin{array}{ll}
      \boldsymbol  v_t = \boldsymbol  v_{t-1} - \alpha_{t-1}\boldsymbol  v_{t-1} - \widehat{\nabla}(\boldsymbol  \theta_{t-s})\eta_t + \mathcal{N}(0, 2 a\eta_t I);\\
      \boldsymbol  \theta_t = \boldsymbol  \theta_{t-1} + \boldsymbol  u_{t-1};\\
      \alpha_t = \alpha_{t-1} + (\frac{1}{n} \boldsymbol  v_t^T\boldsymbol  v_t -\eta_t).
    \end{array}
  \right.
\end{equation}
where $1-a$ is the momentum parameter and $\eta$ is the learning rate in the SGD with momentum.
Again note that to obtain privacy, we need $\frac{2a}{\eta_t} \geq \frac{128NT L^2}{\tau\epsilon^2}\log(\frac{2NT}{\tau\delta})\log(1/\delta)$.

Note that as $\eta_t$ gets smaller, we have the flexibility of choosing $a$ and $\eta_t$ within a reasonable range.

\paragraph{ Stochastic Gradient Fisher Scoring}
Another extension of SGLD is Stochastic Gradient Fisher Scoring (SGFS), where \citet{ahn2012bayesian} proposes to adaptively interpolate between a preconditioned SGLD (see preconditioning \citep{girolami2011riemann}) and a Markov Chain that samples from a normal approximation of the posterior distribution. For parametric problem where Bernstein-von Mises theorem holds, this may be a good idea. The heuristic used in the SGFS is that the covariance matrix of $\boldsymbol  \theta|X$, which is also the inverse Fisher information $I_N^{-1}$ is estimated on the fly. The key features of SGFS is that one can use the stepsize to trade off speed and accuracy, when the stepsize is large, it mixes rapidly to the normal approximation, as the stepsize gets smaller the stationary distribution converges to the true posterior. Further details of SGFS and ideas to privatize it is described in the appendix.

\subsection{Discussions and caveats.}
So far, we have proposed a differentially private Bayesian learning algorithm that is memory efficient, statistically near optimal for a large class of problems, and we can release many intermediate iterates to construct error bars. Given that differential privacy is usually very restrictive, some of these results may appear too good to be true. This is a reasonable suspicion due to the following caveats.

\paragraph{Small $\eta$ helps both privacy and accuracy.} It is true that as $\eta$ goes to $0$, the stationary distribution that these method samples from gets closer to the target distribution. On the other hand, since the variance of the noise we need to add for privacy scales in $O(\eta^2)$ and that for posterior sampling scales like $O(\eta)$, privacy and accuracy benefits from the same underlying principle. The caveat is that we also have a budget on how many samples can we collect. Also the smaller the stepsize $\eta$ is, the slower it mixes, as a result, the samples we collect from the monte carlo sampler is going to be more correlated to each other.

\paragraph{Adaptivity of SGNHT.} While SGNHT is able to adaptively adjust the temperature so that the samples that it produces remain ``unbiased'' in some sense as $\eta\rightarrow 0$. The reality is that if the level of noise is too large, either we adjust the stepsize to be too small to search the space at all, or the underlying stochastic differential equation becomes unstable and quickly diverges. As a result, the adaptivity of SGNHT breaks down if the privacy parameter gets to small.

\paragraph{Computationally efficiency.} For a large problem, it is usually the case that we would like to train with only one pass of data or very small number of data passes. However, due to the condition in Lemma~\ref{lemma:subsampling}, our result does not apply to one pass of data unless $\tau$ is chosen to be as large as $N$. While we can still choose $T$ to be sufficiently large and stop early, but we amount of noise that we add in each iteration will remain the same.

\paragraph{The Curse of Numerical constant.}
The analysis of algorithms often involves larger numerical constants and polylogarithmic terms in the bound. In learning algorithms these are often fine because there are more direct ways to evaluate and compare methods' performances. In differential privacy however, constants do matter. This is because we need to use these bounds (including constants) to decide how much noise or perturbation we need to inject to ensure a certain degree of privacy. These guarantees are often very conservative, but it is intractable to empirically evaluate the actual $\epsilon$ of differential privacy due to its ``worst'' case definition. Our stochastic gradient based differentially private sampler suffers from exactly that. For moderate data size, the product of the constant and logarithmic terms can be as large as a few thousands. That is the reason why it does not perform as well as other methods despite the theoretically being optimal in scaling (the optimality result is due to SGD \citep{bassily2014private}).

\section{Experiments}

Figure~\ref{fig:illus} is a plain illustration of how these stochastic gradient samplers work using a randomly generated linear regression model (note the its posterior distribution will be normal, as the contour illustrates). On the left, it shows how these methods converge like stochastic gradient descent to the basin of convergence. Then it becomes a posterior sampler. The figure on the right shows that the stochastic gradient thermostat is able to produce more accurate/unbiased result and the impact of differential privacy at the level of $\epsilon=10$ becomes negligible.
\begin{figure}
  \centering

  \includegraphics[width=0.45\textwidth]{figs/exp_normal_sampling_eps=10.pdf}
  \includegraphics[width=0.45\textwidth]{figs/exp_normal_sampling_eps=10_zoom_in.pdf}\\
  \caption{Illustration of stochastic gradient langevin dynamics and its private counterpart at $\epsilon=10$.}\label{fig:illus}
\end{figure}

\begin{figure}
  \centering

  \subfigure[Synthetic: classification of two normals.]{
  \includegraphics[width=0.48\textwidth]{figs/Simulated_two_normals.pdf}}
  \subfigure[Abalone: 9 features, 4177 data points.]{
     \includegraphics[width=0.48\textwidth]{figs/UCI_Abalone.pdf}}
     \subfigure[Adult: 109 features, 32561 data points.]{
    \includegraphics[width=0.48\textwidth]{figs/UCI_Adult.pdf}}
  \caption{Comparison of Differential Private methods.}\label{fig:results}
\end{figure}

To evaluate how our proposed methods work in practice, we selected two binary classification datasets: Abalone and Adult, from the first page of UCI Machine Learning Repository and performed privacy constrained logistic regression on them. Specifically, we compared two of our proposed methods, \textsc{OPS}  mechanism and hybrid algorithm against the state-of-the-art empirical risk minimization algorithm \textsc{ObjPert}  \citep{chaudhuri2011differentially,kifer2012private} under varying level of differential privacy protection. The results are shown in Figure~\ref{fig:results}. As we can see from the figure, in both problems, \textsc{OPS}  significantly improves the classification accuracy over \textsc{ObjPert} . The hybrid algorithm also works reasonably well, given that it collected $N$ samples after initializing it from the output of a run of \textsc{OPS}  with privacy parameter $\epsilon/2$. For fairness, we used the $(\epsilon,\delta)$-DP version of the objective perturbation \citep{kifer2012private} and similarly we used Gaussian mechanism (rather than Laplace mechanism) for output perturbation. All optimization based methods are solved using BFGS algorithm to high numerical accuracy. \textsc{OPS}  is implemented using SGNHT and we ran it long enough so that we are confident that it is a valid posterior sample. Minibatch size and number of data passes in the hybrid DP-SGNHT are chosen to be both $\sqrt{N}$.

We note that the plain DP-SGLD and DP-SGNHT without an initialization using \textsc{OPS}  does not work nearly as well. In our experiments, it often performs equally or slightly worse than the output perturbation. This is due to the few caveats (especially ``the curse of numerical constant'') we described earlier.

\section{Related work}\label{sec:relatedwork}
We briefly discuss related work here.
For the first part, we become aware recently that \citet{mir13} and \citet{dimitrakakis2014robust} independently developed the idea of using posterior sampling for differential privacy. \citet[Chapter 5]{mir13} used a probabilistic bound of the log-likelihood to get $(\epsilon,\delta)-DP$ but focused mostly on conjugate priors where the posterior distribution is in closed-form. \citet{dimitrakakis2014robust} used Lipschitz assumption and bounded data points (implies our boundedness assumption) to obtain a generalized notion of differential privacy. Our results are different in that we also studied the statistical and computational properties.
\citet{bassily2014private} used exponential mechanism for empirical risk minimization and the procedure is exactly the same as \textsc{OPS} .  Our difference is to connect it to Bayesian learning and to provide results on limiting distribution, statistical efficiency and approximate sampling. We are not aware of a similar asymptotic distribution with the exception of \citet{smith2008efficient}, where a different algorithm (the subsample-and-aggregate scheme) is proven to give an estimator that is asymptotically normal and efficient (therefore, stronger than our result) under a different set of assumptions. Specifically, \citet{smith2008efficient}'s method requires boundedness of the parameter space while ours method can work with potentially unbounded space so long as the log-likelihood is bounded.

Related to the general topic,  \citet{kasiviswanathan2014semantics} explicitly modeled the ``semantics'' of differential privacy from a Bayesian point of view, \citet{xiao2012bayesian} developed a set of tools for performing Bayesian inference under differential privacy, e.g., conditional probability and credibility intervals. \citet{williams2010probabilistic} studied a related but completely different problem that uses posterior inference as a meta-post-processing procedure, which aims at ``denoising'' the privately obfuscated data when the private mechanism is known. Integrating \citet{williams2010probabilistic} with our procedure might lead to some further performance boost, but investigating its effect is beyond the scope of the current paper.

For the second part, the idea to privately release stochastic gradient has been well-studied. \citet{song2013stochastic,bassily2014private} explicitly used it for differentially private stochastic gradient descent. And \citet{rajkumar2012differentially} used it for private multi-party training.
Our Theorem~\ref{thm:private_SGLD} is a simple modification of Theorem~2.1 in \citet{bassily2014private}. \citet{bassily2014private} also showed that the differential private SGD using Gaussian mechanism with $\tau=1$ matches the lower bound up to constant and logarithmic, so we are confident that not many algorithms can do significantly better than Algorithm~\ref{alg:DP-SGLD}. Our contribution is to point out the interesting algorithmic structures of SGLD and extensions that preserves differential privacy. The method in \citet{song2013stochastic} requires disjoint minibatches in every data pass, and it requires adding significantly more noise in settings when Lemma~\ref{lemma:subsampling} applies. \citet{song2013stochastic} are however applicable when we are doing only a small number of data passes and for these cases, it gets a much better constant. \citet{rajkumar2012differentially}'s setting is completely different as it injects a fixed amount of noise to the gradient corresponds to each data point exactly once. In this way, it replicates objective perturbation \citep{chaudhuri2011differentially} (assuming the method actually finds the optimal solution).

Objective perturbation is originally proposed in \citet{chaudhuri2011differentially} and the $(\epsilon,\delta)$ version that we refer to first appears in \citet{kifer2012private}. Comparing to our two mechanisms that attempts to sample from the posterior, their privacy guarantee requires the solution to be exact while ours does not. In comparison, \textsc{OPS}  estimator is differentially private allows the distribution it samples from to be approximate, DP-SGLD on the other hand releases all intermediate results and every single iteration is public.

\section{Conclusion and future work}
In this paper, we described two simple but conceptually interesting examples that Bayesian learning can be inherently differentially private. Specifically, we show that getting one sample from the posterior is a special case of exponential mechanism and this sample as an estimator is near-optimal for parametric learning. On the other hand, we illustrate that the algorithmic procedures of stochastic gradient Langevin Dynamics (and variants) that attempts to sample from the posterior also guarantee differential privacy as a byproduct. Preliminary experiments suggests that the One-Posterior-Sample mechanism works very well in practice and it substantially outperforms earlier privacy mechanism in logistic regression. While suffering from a large constant, our second method is also theoretically and practically meaningful in that it provides privacy protection in intermediate steps.

To carry the research forward, we think it is important to identify other cases when the existing randomness can be exploited for privacy. Randomized algorithms such as hashing and sketching, dropout and other randomization used in neural networks might be another thing to look at. More on the application end, we hope to explore the one-posterior sample approach in differentially private movie recommendation. Ultimately, the goal is to make differential privacy more practical to the extent that it can truly solve the real-life privacy problems that motivated its very advent.

redpajama_set_name: RedPajamaArXiv


text:
The Jurisdiction Of Federal Courts In Constitutional Cases
The Scope Of National Power
State Sovereignty And Federal Regulation
The Scope Of State Power
The Bill Of Rights, The Civil War Amendments, And Their Inter-Relationship
The Due Process, Contract, And Just Compensation Clauses And The Review Of The Reasonableness Of Legislation
The Equal Protection Clause And The Review Of The Reasonableness Of Legislation
Defining The Scope Of 'Liberty' And 'Property' Protected By The Due Process Clause-The Procedural Due Process Cases
Application Of The Post Civil War Amendments To Private Conduct: Congressional Power To Enforce The Amendments
Governmental Control Of The Content Of Expression
Restrictions On Time, Place, Or Matter Of Expression
Protection Of Penumbral First Amendment Rights
United States v. O'Brien 391 U.S. 367, 88 S. Ct. 1673, 20 L. Ed. 2d 672 (1968)
Texas v. Johnson 491 U.S. 397, 109 S. Ct. 2533, 105 L. Ed. 2d 342 (1989)
City of Erie v. Pap's A.M 529 U.S. 277, 120 S. Ct. 1382, 146 L. Ed. 2d 265, 28 Med. L. Rptr. 1545 (2000)
NAACP v. Alabama 357 U.S. 449, 78 S. Ct. 1163, 2 L. Ed. 2d 1488 (1958)
NAACP v. Claiborne Hardware Co 458 U.S. 886, 102 S. Ct. 3409, 73 L. Ed. 2d 1215 (1982)
Boy Scouts of America v. Dale 530 U.S. 640, 120 S. Ct. 2446, 147 L. Ed. 2d 554 (2000)
Keller v. State Bar of California 496 U.S. 1, 110 S. Ct. 2228, 110 L. Ed. 2d 1 (1990)
Glickman v. Wileman Brothers & Elliott, Inc 521 U.S. 457, 117 S. Ct. 2130, 138 L. Ed. 2d 585, 25 Med. L. Rptr. 1801 (1997)
Pacific Gas and Electric Company v. Public Utilities Commission of California 475 U.S. 1, 106 S. Ct. 903, 89 L. Ed. 2d 1 (1986)
Tasjian v. Republican Party of Connecticut 479 U.S. 208, 107 S. Ct. 544, 93 L. Ed. 2d 514 (1986)
California Democratic Party v. Jones 530 U.S. 567, 120 S. Ct. 2402, 147 L. Ed. 2d 502 (2000)
Buckley v. Valeo 424 U.S. 1, 96 S. Ct. 612, 46 L. Ed. 2d 659 (1976)
First National Bank of Boston v. Bellotti 435 U.S. 765, 98 S. Ct. 1407, 55 L. Ed. 2d 707, 3 Med. L. Rptr. 2105 (1978)
Austin v. Michigan Chamber of Commerce 494 U.S. 652, 110 S. Ct. 1391, 108 L. Ed. 2d 652 (1990)
McIntyre v. Ohio Elections Commission 514 U.S. 334, 115 S. Ct. 1511, 131 L. Ed. 2d 426, 23 Med. L. Rptr. 1577 (1995)
Connick v. Myers 461 U.S. 138, 103 S. Ct. 1684, 75 L. Ed. 2d 708, 1 IER Cases 178 (1983)
United States v. National Treasury Employees Union 513 U.S. 454, 115 S. Ct. 1003, 130 L. Ed. 2d 964, 10 IER Cases 452 (1995)
United States Civil Service Commission v. National Association of Letter Carriers ALF-CIO 413 U.S. 548, 93 S. Ct. 2880, 37 L. Ed. 2d 796 (1973)
Rutan v. Republican Party of Illinois 497 U.S. 62, 110 S. Ct. 2729, 111 L. Ed. 2d 52, 5 IER Cases 673 (1990)
Consolidated Edison Co. of New York v. Public Service Commission 447 U.S.530 (1980)
Cutter v. Wilkinson 544 U.S. 709 (2005)
Legal Services Corporation v. Velazquez 531 U.S. 533 (2001)
Morse v. Frederick 551 U.S. 393 (2007)
United States v. American Library Association, Inc. 533 U.S. 405 (2001)
Religion And The Constitution
Constitutional Law > Constitutional Law Keyed to Cohen > Protection Of Penumbral First Amendment Rights
NAACP v. Claiborne Hardware Co
Citation. 22 Ill.357 U.S. 458 U.S. 886, 102 S. Ct. 3409, 73 L. Ed. 2d 1215 (1982)
Citation22 Ill.357 U.S. 458 U.S. 886, 102 S. Ct. 3409, 73 L. Ed. 2d 1215 (1982)
Brief Fact Summary. Beginning in 1966, under the direction of the Petitioner, the Mississippi National Association for the Advancement of Colored People (NAACP) (Petitioner), black citizens began to boycott the businesses of several white merchants, on the basis of racial injustice. The Respondents, Claiborne Hardware Co. and other merchants (Respondents), brought suit asking for damages, alleging that their businesses had suffered due to the boycott.
Synopsis of Rule of Law. The freedom to associate includes the freedom to demonstration, provided that a demonstration does not lead to violence.
The constitutional guarantees of free speech and free press do not permit a state to forbid or proscribe advocacy of the use of force or law violation except where such advocacy is directed to inciting or producing imminent lawless action and is likely to incite or produce such action.
Facts. Beginning in 1966, under the direction of the Petitioner, black citizens began to boycott the businesses of several white merchants, on the basis of racial injustice. The Respondents brought suit asking for damages, alleging that their businesses had suffered due to the boycott. In 1976, ten years after the beginning of the boycott, the Trial Court held for the Respondents and awarded damages for lost business, in excess of $1.25 million. The Supreme Court of the State of Mississippi upheld the imposition of liability under the theory of malicious interference, and the Petitioner appealed to the United States Supreme Court (Supreme Court).
Issue. This case considers whether demonstrators in a boycott, who are exercising their right to freely associate, can be held liable for damages caused to a business as a result of the boycott.
Held. Reversed.
The Court held that, while a boycott may have the affect of disrupting business, a merchant cannot sue for damages when the demonstration is nonviolent and voluntary. Where, however, violence is used, the individual inciting the violence may be held liable for the damages caused by his actions.
Concurrence. Judge William Rehnquist (J. Rehnquist) concurred
Discussion. Included in the right to freely associate is the right to demonstrate and align one's self with the ideals of the association.
Study Assets: Freedom of Speech: Continued

redpajama_set_name: RedPajamaCommonCrawl


Falls are the number one reason older people are taken to the emergency department in a hospital. Most falls don't cause serious injury but they can leave you distressed. The good news is that there are lots of things you can do to stay steady on your feet.
What Homeowners Need to Know About Hurricanes and Insurance – Far too many Americans aren't aware that flood damage isn't typically covered by homeowners insurance. In this Industry Focus. liability aren't going to cover those damages if a tree falls on that.
Towergate is one of the UK's largest insurance brokers, specialising in cover you really need. Choose a three, six, nine or 12 month policy so you're only paying for the length of cover you really need. Visit the website and buy online today. Nova Insurance, established in 1995, is a nationwide.
BMW innovation lab bears fruit with insurtech deal – The carmaker's UK finance. for bespoke insurance policies that can be managed online. It allows customers to enter details like job and lifestyle, to create a tailored insurance package for car, ho.
Winds of up to 80pmh battered certain parts of the UK on Wednesday and strong gusts caused the roof. the safety of all residents and we are working extremely hard to so do. Tree teams are respondin.
Aug. 25, 2013: Woods falls to the ground in pain during the final round of. Feb. 5, 2015: In typical fashion, fog rolls in.
Finally, you want to make copies of your insurance policy and other critical documents and store that in a waterproof container in your car. Just think – if you're in the middle of a storm, and a tree.
Neil Whyte was asleep in bed when a 50ft tree crashed into. has hit out at their insurance firm and says there's so much w.
TROUTMAN, N.C. – At least four people were injured after a large tree fell on a wagon full of people during a wagon ride at an Iredell County zoo. WBTV reported that at least 50 people were on the wag.
A man and child escaped with minor injuries after a tree fell onto a moving car in Alnwick. Emergency services including para.
Dollar Tree are inviting customers to take part in the www.dollartreefeedback.com Customer Feedback Survey and be in with a chance to.
On November 27, 2009 reports emerged that Woods had been injured in a car accident near his Florida home after colliding with.
This year's Notte Bianca falls on 6 October but if you can't make that date. on a B&B basis, including flights and car hir.
If a tree falls on a car parked in a driveway, the policy would cover the removal of the tree. Auto insurance, if applicable, would pay for any repairs to the vehicle. If, however, the tree falls harm.
Dear Matthew, You say your car is an 05 – is it still therefore under the 3 year manufacturer warranty? If so there is an extremely good chance that Vauxhall will cover this (especially as, if the car is mechanically dubious, it.
Storm Ali: Two in hospital after tree falls onto moving car in Alnwick – Two people have been taken to hospital after a tree fell on a moving car in Alnwick. Emergency services including paramedics, police and the fire service were called to Bondgate Without in the town on.


No downloading. No installing. No waiting. Microsoft Access 2016 is configured and ready to use.
Access 2016 lets you easily create database apps.
Access contains Wizards that walk you through each step of the way. The user interface is intuitive; accelerating data information retrieval.
Access gives data managers a fully functional, relational database management system in minutes.
It also can be used in the front-end as back-end tables with products like Microsoft SQL Server and non-Microsoft products like Oracle and Sybase.


text:
S. Gresta
Istituto di Geologia e Geofisica, Università di Catania, Italy
G. Lombardo
R. Cristofolini
Istituto di Scienze della Terra, Università di Catania, Italy
Home > Vol 39, No 2 (1996) >	Gresta
Characteristics of volcanic tremor accompanying the September 24th, 1986 explosive eruption of Mt. Etna (Italy)
S. Gresta, G. Lombardo, R. Cristofolini
Features of the volcanic tremor recorded before, during and after the eruptive event which occurred at Mt. Etna on September 24th 1986, are described. The whole eruption was particularly short in time (about eight hours) and characterized by an extremely violent explosive activity with lava fountains a few hundred meters high. As the complete record of the seismic signals generated during the whole eruptive episode was available, a detailed spectral analysis of the volcanic tremor recorded at four stations, located at increasing distance from the summit of the volcano, was carried out. Fourier analysis, that was performed using temporal windows of about 11 min in duration, pointed to some large fluctuations of the overall spectral amplitude, as well as some frequency variations of the dominant spectral peaks. The ratio of the overall spectral amplitude recorded at the highest station and at the peripheral ones, was calculated in the two spectral bands 1.0-2.5 and 2.6-6.0 Hz, respectively. The significant contribution of energy at low frequency values supports the hypothesis of a subvertical planar source, which was active during the paroxysmal stage of the eruption. Such results are also supported by the analysis of the attenuation function of the spectral amplitude.
Mt. Etna;summit paroxysmal eruption;volcanic tremor
DOI: https://doi.org/10.4401/ag-3976


Caroline Kennedy to Replace Hillary in Senate?
How Bad is the Kidnapping Problem in Mexico?
Jesse Jackson Jr. the "Informant": Payback?
Iraq Shoe Hurler Seeking Pardon, It Was "An Ugly Act"
Hey, Sarah, I Can See The Abyss From Here!
Is Oprah Moving Closer to Obama's Kitchen Cabinet?


text:
Biografia
Nato e cresciuto in Louisiana, dopo aver lasciato il college Alexander prestò servizio militare per l'Air Force Reserve Command e successivamente entrò in politica con il Partito Democratico. Con questo schieramento, risultò eletto alla Camera dei rappresentanti della Louisiana nel 1988 e vi restò per i successivi quattordici anni.

Nel 2002 si candidò alla Camera dei Rappresentanti e vinse le elezioni, divenendo deputato. Due anni dopo chiese un altro mandato, ma cambiando schieramento e candidandosi con il Partito Repubblicano; nonostante il cambio di casacca, riuscì a farsi rieleggere e ottenne negli anni successivi altri quattro mandati.

Nel 2013 lasciò il seggio per accettare la carica di Segretario degli Affari dei Veterani della Louisiana all'interno del gabinetto del governatore Bobby Jindal.

Durante la sua permanenza al Congresso, Alexander fu un repubblicano conservatore, vicino alle posizioni del Tea Party.

Altri progetti

Collegamenti esterni
Rodney Alexander sul Biographical Directory of the United States Congress

Politici del Partito Democratico (Stati Uniti d'America)
Politici del Partito Repubblicano (Stati Uniti d'America)
Rappresentanti statunitensi eletti dalla Louisiana

redpajama_set_name: RedPajamaWikipedia