text:
\section{Introduction}\label{sec:intro}
Stochastic gradient descent ({\sf SGD}), originally introduced in \cite{RM1951} under the name of stochastic approximation {\sf SA}, is probably the most efficient and powerful method for solving optimization problems in machine learning. In this context, we want to optimize an (unknown) objective function $f$ defined over a large set of collected data, while we only have an access to the noisy samples of the gradient $\nabla f$ of $f$. At a point $x$, we observe a random vector $G(x, \xi)$, a sample of $\nabla f(x)$, where $\xi$ is some random variable.  Through a careful choice of step sizes, the ``noise'' induced by this randomness can be averaged out across iterations, and the algorithm converges to stationary point of $f$. Such convergence is established based on two standard assumptions, the gradient samples are i.i.d and unbiased, i.e., $\mathbb{E}[G(x,\xi)] = \nabla f(x)$ \cite{GhadimiL2013,bottou2016optimization,Nguyen2018_sgdhogwild,Nguyen2019_sgd_new_aspects}. For more details about the results of {\sf SGD} under this setting can be found in the recent review paper \cite{bottou2016optimization}.

In this paper, we show that a particular version of {\sf SGD} is still ergodic when the gradients of the underlying objective function are sampled from Markov processes, and hence are biased and not independent across iterations. It has been observed that the {\sf SGD} performs better when the gradients are sampled from Markov process as compared to i.i.d samples in both convex and nonconvex problems \cite{SunSY2018}. This model for the gradients has been considered previously in \cite{DuchiAJJ2012, SunSY2018,JohanssonRJ2010,RamNV2009,DoanNPR2020}, where different variants of {\sf SGD} are considered. In particular, the Markov subgradient incremental methods have been considered in \cite{RamNV2009,JohanssonRJ2010} motivated by the applications of distributed algorithms to minimize a sum of functions over a network of agents. At any iteration, an agent updates the current iterates using its own function, and either passes the new iterate to a randomly chosen neighbor or keeps updating. In \cite{DuchiAJJ2012}, the authors consider an ergodic version of the popular mirror descent and provide a finite-time analysis for the case of convex optimization problems. The authors in \cite{SunSY2018} study a non-ergodic version of {\sf SGD} for both convex and nonconvex problems when the Markov chains is non-reversible. They establish a convergence rate ${\cal O}(1/k^{1-q}), q\in(1/2,1)$, which is worse than ${\cal O}(1/\sqrt{k})$ under i.i.d sampling. Finally, the authors in \cite{DoanNPR2020} consider an accelerated ergodic version of {\sf SGD} for both nonconvex and convex problems and achieve the same rates as the ones using i.i.d samples, except for a log factor capturing the mixing time of the underlying Markov chain.

The convergence analysis of the existing works listed above is established under the assumptions on the boundedness of the iterates, e.g., either the feasible set is compact or the gradient is bounded. Such assumptions may not be applicable in many settings, for example, in the context of reinforcement learning ({\sf RL}), which is the main motivation of this paper. Thus, our goal in this paper is to study the convergence rates of {\sf SGD} under Markov randomness for different settings under less restrictive assumptions as compared to the existing works \cite{DuchiAJJ2012, SunSY2018,JohanssonRJ2010,RamNV2009,DoanNPR2020}. We also note some relevant works in \cite{SrikantY2019_FiniteTD,ChenZDMC2019,Karimi_colt2019}, where the authors study finite-time analysis of stochastic approximation under Markov randomness. We, however, focus on the convergence rates of {\sf SGD} under different settings than the ones considered in \cite{SrikantY2019_FiniteTD,ChenZDMC2019,Karimi_colt2019}.

\subsection{Main contributions}
We study the popular stochastic gradient descent where the gradients are sampled from
a Markov process. We show that, despite the gradients being biased and dependent across iterations, the convergence rate across many different types of objective functions (strongly convex, smooth and satisfying error bound conditions,
nonconvex and smooth) is within a logarithmic factor of the comparable bounds for independent gradients. This logarithmic factor is naturally related to the mixing time of the underlying Markov process generating the stochastic gradients. Our convergence analysis is established without requiring any assumption on the boundedness of the iterates or the gradients, as often assumed in the existing literature.

\section{Stochastic gradient descent under Markov randomness}
In this section, we present the main problem considered in this paper, which is inspired by the work in \cite{DuchiAJJ2012}. Specifically, we consider the following (possibly nonconvex) optimization problem
\begin{align}
\underset{x\in\mathbb{R}^{d}}{\text{minimize}}\; f(x) ,\label{sec_optimization:prob}
\end{align}
where $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is given as
\begin{align}
f(x) \triangleq \mathbb{E}_{\mu}[{\cal G}(x;\xi)] = \int_{{\cal S}}{\cal G}(x;\xi)d\mu(\xi).\label{sec_optimization:notation_f}
\end{align}
Here ${\cal S}$ is a finite statistical sample space with probability distribution $\mu$ and ${\cal G}(\cdot,\xi):{\cal S}\rightarrow\mathbb{R}$ is a bounded below (possibly nonconvex) function  associated with $\xi\in{\cal S}$. We are interested in the first-order stochastic optimization methods, specifically the popular {\sf SGD}, for solving problem \eqref{sec_optimization:prob}. In particular, we assume that we only have access to $G(x;\xi)\in\partial {\cal G}(x;\xi)$, the (sub)gradient of ${\cal G}(\cdot;\xi)$ evaluated at the point $x$. Starting with an arbitrarily initial condition $x_{0}\in{\cal X}$, {\sf SGD} iteratively updates the iterates as
\begin{align}
x_{k+1} = x_{k} - \alpha_{k} G(x_{k},\xi_{k}), \label{sec_SGD:alg}
\end{align}
where $\alpha_{k}$ is some nonincreasing and nonnegative time-varying step sizes. We consider in this paper the case where the samples $\xi$ are generated from an ergodic Markov process, whose stationary distribution is $\mu$. Our focus is to study the finite-time analysis of {\sf SGD} under such Markov randomness on different assumptions of the objective function $f$. To do that, we introduce the following technical assumptions used throughout this paper.

\subsection{Assumptions and Preliminaries}
Given a vector $x\in\mathbb{R}^{d}$, we associate with it a norm $\|\cdot\|$ and denote its dual norm as $\|\cdot\|_{*}$, i.e.,
\begin{align*}
\|x\|_{*} = \sup_{\|y\|\leq 1}\langle x,y\rangle,
\end{align*}
where $\langle \cdot,\cdot\rangle$ denotes the inner product. Using the Cauchy-Schwarz inequality we obtain
\begin{align}
|\langle x,y\rangle| \leq \|x\|_{*}\|y\|.
\end{align}
Moreover, by \eqref{sec_SGD:alg} we have
\begin{align}
\|x_{k+1}-x_{k}\| \leq \alpha_{k}\|G(x_{k},\xi_{k})\|_{*}.\label{sec_SGD_sc:lem_xk_ineq}
\end{align}
We first assume that problem \eqref{sec_optimization:prob} is well-defined.
\begin{assump}\label{assump:optimal_set}
The optimal set ${\cal X}^*$ of \eqref{sec_optimization:prob} is nonempty, i.e., there exists $x^*$ s.t. $f(x^*) = \min_{x} f(x)$.
\end{assump}
We consider the following fairly standard technical assumptions about the Markov process, which are often assumed in the existing literature  \cite{DuchiAJJ2012, SunSY2018, SrikantY2019_FiniteTD,ChenZDMC2019, Doan2019, DoanNPR2020, DoanMR2019_DTD}.

\begin{assump}\label{assump:stationary}
The sequence $\{\xi_{k}\}$ is a Markov chain with a finite state space ${\cal S}$. In addition, the following limits exit
\begin{align}
\lim_{k\rightarrow\infty}
\mathbb{E}[G(x;\xi_{k})] = g(x)\in\partial f(x)\quad \forall x.
\end{align}
\end{assump}
\begin{assump}\label{assump:mix}
Given a positive constant $\alpha$, we denote by $\tau(\alpha)$ the mixing time of the Markov chain $\{\xi_{k}\}$. We assume that for $g(x) \in \partial f(x)$ and $\forall\;\xi\in{\cal S}$
\begin{align*}
&\left\|\mathbb{E}[G(x;\xi_{k})] - g(x)\,|\, \xi_{0} = \xi\right\|_{*} \leq \alpha,\quad \forall  k\geq \tau(\alpha).
\end{align*}
Moreover, $\{\xi_{k}\}$ has a geometric mixing time, i.e., there exists a positive constant $C$ such that \begin{align}
\tau(\alpha) = C\log\left(\frac{1}{\alpha}\right).\label{notation:tau}
\end{align}
\end{assump}
Next we assume that $G(x,\cdot)$ is uniformly Lipschitz continuous, which is satisfied in the context of {\sf RL} studied in \cite{ChenZDMC2019,SrikantY2019_FiniteTD}. Moreover, this condition is weaker than the boundedness assumptions in \cite{DuchiAJJ2012, SunSY2018,JohanssonRJ2010,RamNV2009,DoanNPR2020}.

\begin{assump}\label{assump:Lipschitz_sample}
There exists a constant $M$ such that for all $\xi\in{\cal S}$
\begin{align}
\|G(x,\xi)\|_{*}   \leq M (\|x\|+1)\qquad \text{and}\qquad \|g(x)\|_{*}   \leq M (\|x\|+1),\qquad \forall x\in{\cal X}, g(x)\in\partial f(x).  \label{assump:Lipschitz_sample:ineq}
\end{align}
\end{assump}
For convenience, we introduce the following notation
\begin{align}
\alpha_{k;\tau(\alpha_{k})} =     \sum_{u = k-\tau(\alpha_{k})}^{k-1}\alpha_{u},\label{sec_SGD_sc:notation_alpha_tau}
\end{align}
where $\tau(\alpha_{k})$ is the mixing time defined in Assumption \ref{assump:mix} associated with the step size $\alpha_{k}$. Note that $\tau(\alpha_{k}) = \log(1/\alpha_{k})$ . Moreover, we consider in this paper diminishing step size $\alpha_{k}$, therefore, $\lim_{k\rightarrow\infty}\tau(\alpha_{k})\alpha_{k} = 0$. This implies that there exists a positive integer ${\cal K}^*$ such that
\begin{align}
\alpha_{k;\tau(\alpha_{k})}\leq \tau(\alpha_{k})\alpha_{k-\tau(\alpha_{k})}\leq \frac{\log(2)}{M},\qquad \forall k \geq {\cal K}^*.  \label{sec_SGD:notation_K*}
\end{align}
Finally, we consider the following important lemma to provide an upper bound of the iterates generated by {\sf SGD}. This result is used throughout this paper to derive the rates of {\sf SGD}.
\begin{lem}\label{sec_SGD_sc:lem_xk_bounded}
Suppose that Assumptions \ref{assump:stationary}--\ref{assump:Lipschitz_sample} hold. Let $\{x_{k}\}$ be generated by \eqref{sec_SGD:alg}. Then for all $k\geq {\cal K}^*$
\begin{align}
&\|x_{k}-x_{k-\tau(\alpha_{k})}\|\leq 6M\alpha_{k;\tau(\alpha_{k})}\|x_{k}\| + 6M\alpha_{k;\tau(\alpha_{k})}\leq 2\|x_{k}\| + 2.   \label{sec_SGD_sc:lem_xk_bounded_ineq2}
\end{align}
\end{lem}

\begin{proof}
Using \eqref{assump:Lipschitz_sample:ineq}, \eqref{sec_SGD_sc:lem_xk_ineq}, and the triangle inequality we have
\begin{align}
\|x_{k+1}\| - \|x_{k}\| \leq \|x_{k+1} - x_{k}\| \leq \alpha_{k}\|G(x_{k},\xi_{k})\|_{*} \leq M\alpha_{k}(\|x_{k}\|+1),\label{sec_SGD_sc:lem_xk_bounded_Eq1a}
\end{align}
which gives
\begin{align*}
\|x_{k+1}\| \leq (1+M\alpha_{k})\|x_{k}\| + M\alpha_{k}.
\end{align*}
Using the relation $1+x \leq e^{x}$ for all $x\geq 0$, the preceding relation gives for all $t\in[k-\tau(\alpha_{k}),k-1]$
\begin{align*}
\|x_{t}\| &\leq \prod_{u = k-\tau(\alpha_{k})}^{t-1}(1+M\alpha_{u})\|x_{k-\tau(\alpha_{k})}\| + M\sum_{u = k-\tau(\alpha_{k})}^{t-1}\alpha_{u}\prod_{\ell=u+1}^{t-1}(1 + M\alpha_{\ell})\notag\\
&\leq \exp\left\{M\sum_{u=k-\tau(\alpha_{k})}^{t-1}\alpha_{u}\right\}\|x_{k-\tau(\alpha_{k})}\| + M\sum_{u = k-\tau(\alpha_{k})}^{t-1}\alpha_{u}\exp\left\{M\sum_{\ell = u+1}^{t-1}\alpha_{\ell}\right\}\notag\\
&\leq \exp\left\{M\tau(\alpha_{k})\alpha_{k-\tau(\alpha_{k})}\right\}\|x_{k-\tau(\alpha_{k})}\| + M\sum_{u = k-\tau(\alpha_{k})}^{t-1}\alpha_{u}\exp\left\{M\tau(\alpha_{k})\alpha_{k-\tau(\alpha_{k})}\right\}.
\end{align*}
Recall from \eqref{sec_SGD:notation_K*} that for all $k\geq {\cal K}^*$
\begin{align*}
M\tau(\alpha_{k})\alpha_{k-\tau(\alpha_{k})}\leq \log(2) \leq \frac{1}{2}\cdot
\end{align*}
Thus, by using \eqref{sec_SGD_sc:notation_alpha_tau} we have from the equation above for all $t\in[k-\tau(\alpha_{k}),k-1]$
\begin{align*}
\|x_{t}\| &\leq  2\|x_{k-\tau(\alpha_{k})}\| + 2M\sum_{u = k-\tau(\alpha_{k})}^{t-1}\alpha_{u} = 2\|x_{k-\tau(\alpha_{k})}\| + 2M\alpha_{k;\tau(\alpha_{k})}.
\end{align*}
Using the preceding relation we have from \eqref{sec_SGD_sc:lem_xk_bounded_Eq1a} for all $k\geq {\cal K}^*$
\begin{align*}
\|x_{k}-x_{k-\tau(\alpha_{k})}\|&\leq \sum_{t=k-\tau(\alpha_{k})}^{k-1}\|x_{t+1} - x_{t}\|\leq \sum_{t=k-\tau(\alpha_{k})}^{k-1}M\alpha_{t}(\|x_{t}\| + 1)\notag\\
&\leq \sum_{t=k-\tau(\alpha_{k})}^{k-1}L\alpha_{t}\left(2\|x_{k-\tau(\alpha_{k})}\| + 2M\alpha_{k;\tau(\alpha_{k})}\right) + M\alpha_{k;\tau(\alpha_{k})}\notag\\
&\leq 2M\alpha_{k;\tau(\alpha_{k})}\|x_{k-\tau(\alpha_{k})}\| + 2M\alpha_{k;\tau(\alpha_{k})},
\end{align*}
where the last inequality is due to \eqref{sec_SGD:notation_K*}. Using the preceding inequality and the triangle inequality yields
\begin{align*}
\|x_{k}-x_{k-\tau(\alpha_{k})}\|&\leq 2M\alpha_{k;\tau(\alpha_{k})}\|x_{k} - x_{k-\tau(\alpha_{k})}\| + 2M\alpha_{k;\tau(\alpha_{k})}\|x_{k}\| + 2M\alpha_{k;\tau(\alpha_{k})}\notag\\
&\leq \frac{2}{3}\|x_{k} - x_{k-\tau(\alpha_{k})}\| + 2M\alpha_{k;\tau(\alpha_{k})}\|x_{k}\| + 2M\alpha_{k;\tau(\alpha_{k})},
\end{align*}
where the last inequality we use \eqref{sec_SGD:notation_K*} to  have $L\alpha_{k;\tau(\alpha_{k})}\leq \log(2)\leq 1/3$. Rearranging the equation above yields \eqref{sec_SGD_sc:lem_xk_bounded_ineq2}
\begin{align*}
 \|x_{k}-x_{k-\tau(\alpha_{k})}\| \leq  6M\alpha_{k;\tau(\alpha_{k})}\|x_{k}\| + 6M\alpha_{k;\tau(\alpha_{k})}\leq 2\|x_{k}\| + 2.
\end{align*}
\end{proof}

\section{Finite-time analysis of {\sf SGD} under Markov randomness}\label{sec:SGD:analysis}
In this section, we focus on analyzing the finite-time performance of {\sf SGD} under Markov randomness for different assumptions on the objective function $f$. In particular, we consider three different cases, namely, $f$ is strongly convex, $f$ is smooth and satisfies an error bound condition, and $f$ is only smooth and nonconvex. A key observation of our results is that {\sf SGD} under Markov randomness has the same finite-time convergence as the one under i.i.d samples and unbiased estimate, except for a $\log$ factor capturing the impact of geometric mixing time of the underlying Markov processes. More details are given as below.

\subsection{Convergence analysis: strong convexity}
We study here the convergence rates of {\sf SGD} \eqref{sec_SGD:alg} when the function $f$ is strongly convex, i.e., we consider the following assumption.
\begin{assump}\label{assump:sc}
There exists a constant $\sigma > 0$ such that $f$ satisfies
\begin{align}
f(x) - f(y) - \langle g(y),x-y\rangle \geq \frac{\sigma}{2}\|x-y\|^2,\qquad g(y) \in\partial f(y).     \label{assump_sc:ineq}
\end{align}
\end{assump}
Under this assumption, there exists a unique optimal solution $x^*$ of \eqref{sec_optimization:prob}, i.e., ${\cal X}^* = {x^*}$. In this section, we consider the norm induced by the inner product, so, $\|\cdot\|$ and $\|\cdot\|_{*}$ are the same.  Recall that ${\cal K}^*$ is a positive integer satisfying \eqref{sec_SGD:notation_K*}. With some abuse of notation, we consider in this section  ${\cal K}^*$ satisfying
\begin{align}
\left\{\begin{array}{l}
\tau(\alpha_{k})\alpha_{k-\tau(\alpha_{k})}\leq \max\left\{\frac{\log(2)}{M},\;\frac{\sigma}{8(25M^2+1)}\right\}\\
\ln\left(\frac{\sigma k}{4}\right)\leq \frac{k}{2}
\end{array}\right.\qquad \forall k \geq {\cal K}^*,   \label{sec_SGD_sc:notation_K*}
\end{align}
which also satisfies \eqref{sec_SGD:notation_K*}. Our main result in this section is to show that $x_{k}$ converges to $x^*$ in expectation at a rate
\begin{align}
\mathbb{E}\left[\|x_{k}-x^*\|^2\right]  \lesssim {\cal O}\left(\frac{\mathbb{E}\left[\|x_{{\cal K}^*}-x^*\|^2\right]}{k^2} + \frac{\log(k)}{k}\right).
\end{align}
To derive this rate, we  consider the following two key lemmas. The first lemma is to provide an upper bound on the function value.
\begin{lem}\label{sec_SGD_sc:lem_f_fk}
Suppose that Assumptions \ref{assump:sc} holds. Let $\{x_{k}\}$ be generated by \eqref{sec_SGD:alg}. Then we have for any $x$
\begin{align}
f(x_{k}) - f(x) &\leq \frac{1-\sigma\alpha_{k}}{2\alpha_{k}}\|x-x_{k}\|^2 - \frac{1}{2\alpha_{k}} \|x-x_{k+1}\|^2 + L^2\alpha_{k}(\|x_{k}\|^2+1)\notag\\
&\qquad
-  \langle G(x_k;\xi_{k}) - g(x_{k}), x_{k} -  x\rangle \rangle.\label{sec_SGD_sc:lem_f_fk_bounded:ineq}
\end{align}
\end{lem}

\begin{proof}
By the strong convexity of $f$, Eq.\ \eqref{assump_sc:ineq}, we have for all $x\in\mathbb{R}^{d}$ and $g(x_{k})\in\partial f(x_{k})$
\begin{align}
f(x_{k}) - f(x) &\leq  g(x_k)^T( x_{k} -  x) - \frac{\sigma}{2}\|x_{k}-x\|^2 \notag\\
&=  \langle G(x_k;\xi_{k}), x_{k+1} -  x\rangle + \langle G(x_k;\xi_{k}), x_{k} -  x_{k+1}\rangle\notag\\
&\qquad - \langle G(x_k;\xi_{k}) - g(x_{k}), x_{k} -  x \rangle - \frac{\sigma}{2}\|x_{k}-x\|^2.\label{sec_SGD_sc:lem_f_fk:Eq1a}
\end{align}
By \eqref{sec_SGD:alg} we have
\begin{align*}
\alpha_{k}\langle G(x_{k},\xi_{k}),x_{k+1}-x\rangle =    \langle x_{k}-x_{k+1}, x_{k+1} - x \rangle = \frac{1}{2}\left[\|x-x_{k}\|^2 - \|x-x_{k+1}\|^2 - \|x_{k}-x_{k+1}\|^2\right].
\end{align*}
Substituting the preceding relation into \eqref{sec_SGD_sc:lem_f_fk:Eq1a} yields \eqref{sec_SGD_sc:lem_f_fk_bounded:ineq}, i.e.,
\begin{align*}
f(x_{k}) - f(x) &\leq \frac{1-\sigma\alpha_{k}}{2\alpha_{k}}\|x-x_{k}\|^2 - \frac{1}{2\alpha_{k}} \|x-x_{k+1}\|^2 - \frac{1}{2\alpha_{k}} \|x_{k}-x_{k+1}\|^2\notag\\ &\qquad + \langle G(x_k;\xi_{k}), x_{k} -  x_{k+1} \rangle  - \langle G(x_k;\xi_{k}) - g(x_{k}), x_{k} -  x \rangle \notag\\
&\leq \frac{1-\sigma\alpha_{k}}{2\alpha_{k}}\|x-x_{k}\|^2 - \frac{1}{2\alpha_{k}} \|x-x_{k+1}\|^2 + \frac{\alpha_{k}\|G(x_{k};\xi_{k})\|_{*}^2}{2}\notag\\
&\qquad -  \langle G(x_k;\xi_{k}) - g(x_{k}), x_{k} -  x \rangle\notag\\
&\leq \frac{1-\sigma\alpha_{k}}{2\alpha_{k}}\|x-x_{k}\|^2 - \frac{1}{2\alpha_{k}} \|x-x_{k+1}\|^2 + L^2\alpha_{k}(\|x_{k}\|^2+1)\notag\\
&\qquad
-  \langle G(x_k;\xi_{k}) - g(x_{k}), x_{k} -  x \rangle,
\end{align*}
where the second and last inequalities are due to the Cauchy-Schwarz inequality and \eqref{assump:Lipschitz_sample:ineq}, respectively.
\end{proof}
The next lemma provides an upper bound for the last term on the right-hand side of \eqref{sec_SGD_sc:lem_f_fk_bounded:ineq}.
\begin{lem}\label{sec_SGD_sc:lem_bias}
Suppose that Assumptions \ref{assump:stationary}--\ref{assump:Lipschitz_sample} hold. Let $\{x_{k}\}$ be generated by \eqref{sec_SGD:alg}. Then $\forall k\geq {\cal K}^*$ and $x\in\mathbb{R}^{n}$ we have
\begin{align}
\mathbb{E}\left[\langle G(x_k;\xi_{k}) - g(x_{k}), x_{k} -  x \rangle\right] \leq \left(\alpha_{k}+24M^2\alpha_{k;\tau(\alpha_{k})}\right)\mathbb{E}\left[\|x_{k}\|^2\right] + 3\alpha_{k} + 24M^2\alpha_{k;\tau(\alpha_{k})}.     \label{sec_SGD_sc:lem_bias:ineq}
\end{align}
\end{lem}

\begin{proof}
Consider
\begin{align}
\langle G(x_k;\xi_{k}) - g(x_{k}), x_{k} -  x \rangle =  \langle G(x_k;\xi_{k}) - g(x_{k}), x_{k} -  x_{k-\tau(\alpha_{k})} \rangle + \langle G(x_k;\xi_{k}) - g(x_{k}), x_{k-\tau(\alpha_{k})} -  x \rangle.
\label{sec_SGD_sc:lem_bias:Eq1}
\end{align}
We next analyze each term on the right-hand side of \eqref{sec_SGD_sc:lem_bias:Eq1a}. Let ${\cal F}_{k}$ be the filtration containing all the information generated by {\sf SGD} up to iteration $k$. First, by Assumption \eqref{assump:mix} we have
\begin{align}
&\mathbb{E}\left[\langle G(x_k;\xi_{k}) - g(x_{k}), x_{k-\tau(\alpha_{k})} -  x \rangle\,|\,{\cal F}_{k-\tau(\alpha_{k})}\right] = \left\langle \mathbb{E}[G(x_k;\xi_{k}) - g(x_{k})\,|\,{\cal F}_{k-\tau(\alpha_{k})}], x_{k-\tau(\alpha_{k})} -  x \right\rangle\notag\\
&\leq \|x_{k-\tau(\alpha_{k})} -  x\|\left|\mathbb{E}[G(x_k;\xi_{k}) - g(x_{k})\,|\,{\cal F}_{k-\tau(\alpha_{k})}]\right|\leq \alpha_{k}\|x_{k-\tau(\alpha_{k})} -  x\| \stackrel{\eqref{sec_SGD_sc:lem_xk_bounded_ineq2}}{\leq} 2\alpha_{k} \|x_{k}\| + 2\alpha_{k}\notag\\
&\leq \alpha_{k}\|x_{k}\|^2 + 3\alpha_{k},   \label{sec_SGD_sc:lem_bias:Eq1a}
\end{align}
where the third inequality we use \eqref{sec_SGD_sc:notation_K*} to have $\alpha_{k;\tau(\alpha_{k})}\leq \log(2)/M\leq 1/3$ and the last inequality is due to Cauchy-Schwarz inequality. Second, using \eqref{assump:Lipschitz_sample:ineq} we consider
\begin{align}
&\langle G(x_k;\xi_{k}) - g(x_{k}), x_{k} -  x_{k-\tau(\alpha_{k})} \rangle \leq \left\|\langle G(x_k;\xi_{k}) - g(x_{k}), x_{k} -  x_{k-\tau(\alpha_{k})} \rangle\right\|\notag\\
&\leq \left(\|G(x_k;\xi_{k})\| + \|g(x_{k})\|\right)\|x_{k} -  x_{k-\tau(\alpha_{k})}\| \leq 2M(\|x_{k}\|+1)\|x_{k} -  x_{k-\tau(\alpha_{k})}\|\notag\\
&\stackrel{\eqref{sec_SGD_sc:lem_xk_bounded_ineq2}}{\leq} 12M^2\alpha_{k;\tau(\alpha_{k})} (\|x_{k}\|+1)^2\leq 24M^2\alpha_{k;\tau(\alpha_{k})}\|x_{k}\|^2 + 24M^2\alpha_{k;\tau(\alpha_{k})}.  \label{sec_SGD_sc:lem_bias:Eq1b}
\end{align}
Taking the expectation on both sides of \eqref{sec_SGD_sc:lem_bias:Eq1} and using \eqref{sec_SGD_sc:lem_bias:Eq1a} and \eqref{sec_SGD_sc:lem_bias:Eq1b} we obtain \eqref{sec_SGD_sc:lem_bias:ineq}.
\end{proof}
We now state the main result of this section in the following theorem, where we study the convergence rate of {\sf SGD} when $f$ is strongly convex.
\begin{thm}\label{sec_SGD_sc:thm_rate}
Suppose that Assumptions \ref{assump:stationary}--\ref{assump:sc} hold. Let $\{x_{k}\}$ be generated by \eqref{sec_SGD:alg}. Let $\alpha_{k}$ be
\begin{align}
\alpha_{k} = \frac{4}{\sigma k}.    \label{sec_SGD_sc:thm_rate:stepsize}
\end{align}
Then we have for all $k\geq {\cal K}^*$, where ${\cal K}^*$ is defined in \eqref{sec_SGD_sc:notation_K*}
\begin{align}
\mathbb{E}[\|x_{k+1}-x^*\|^2]\leq \frac{{\cal K}^{*}({\cal K}^{*}-2)}{k^2}\mathbb{E}[\|x_{{\cal K}^{*}}-x^*\|^2] + \frac{320(15M^2+1)\log(\sigma k/4)}{k\sigma}\cdot    \label{sec_SGD_sc:thm_rate:ineq}
\end{align}
\end{thm}
\begin{proof}
Taking the expectation on both sides of  \eqref{sec_SGD_sc:lem_f_fk_bounded:ineq} and using \eqref{sec_SGD_sc:lem_bias:ineq} we have for $x=x^*$,
\begin{align*}
\mathbb{E}[f(x_{k})] - f(x^*) &\leq \frac{1-\sigma\alpha_{k}}{2\alpha_{k}}\mathbb{E}[\|x_{k}-x^*\|^2] - \frac{1}{2\alpha_{k}}\mathbb{E}[\|x_{k+1}-x^*\|^2] + M^2\alpha_{k}(\mathbb{E}\left[\|x_{k}\|^2\right]+1)\notag\\
&\qquad +  \left(\alpha_{k}+24M^2\alpha_{k;\tau(\alpha_{k})}\right)\mathbb{E}\left[\|x_{k}\|^2\right] + 3\alpha_{k} + 24M^2\alpha_{k;\tau(\alpha_{k})}\notag\\
&\leq \frac{1-\sigma\alpha_{k}}{2\alpha_{k}}\mathbb{E}[\|x_{k}-x^*\|^2] - \frac{1}{2\alpha_{k}}\mathbb{E}[\|x_{k+1}-x^*\|^2] \notag\\
&\qquad + (25M^2+1)\alpha_{k;\tau(\alpha_{k})}\mathbb{E}\left[\|x_{k}\|^2\right] + (3+25M^2)\alpha_{k;\tau(\alpha_{k})}\notag\\
&\leq \frac{1-\sigma\alpha_{k}}{2\alpha_{k}}\mathbb{E}[\|x_{k}-x^*\|^2] - \frac{1}{2\alpha_{k}}\mathbb{E}[\|x_{k+1}-x^*\|^2]\notag\\
&\qquad   + (50M^2+2)\alpha_{k;\tau(\alpha_{k})}\mathbb{E}\left[\|x_{k}-x^*\|^2\right] + 5(1+15M^2)\alpha_{k;\tau(\alpha_{k})},
\end{align*}
where the second inequality we use $\alpha_{k}\leq \alpha_{k;\tau(\alpha_{k})}$ and the last inequality is due to the Cauchy-Schwarz inequality. Since $f(x_{k})-f^*\geq 0$, by multiplying both sides by $k$ we obtain
\begin{align}
0&\leq \frac{(1-\frac{\sigma}{2}\alpha_{k})k}{2\alpha_{k}}\mathbb{E}[\|x_{k}-x^*)\|^2 - \frac{k}{2\alpha_{k}}\mathbb{E}[\|x_{k+1}-x^*\|^2]\notag\\
&\qquad - \frac{\sigma k}{4}\mathbb{E}[\|x_{k}-x^*\|^2]   + (50M^2+2)k\alpha_{k;\tau(\alpha_{k})}\mathbb{E}\left[\|x_{k}-x^*\|^2\right] + 5(1+15M^2)k\alpha_{k;\tau(\alpha_{k})}.\label{sec_SGD_sc:thm_rate:eq1}
\end{align}
Recall that $\alpha_{k} = 4/\sigma k$ we have
\begin{align*}
&\frac{(1-\frac{\sigma}{2}\alpha_{k})k}{\alpha_{k}} = \frac{\sigma k(k-2)}{4} \leq \frac{\sigma (k-1)^2}{4},\qquad \forall k\geq 1.
\end{align*}
By \eqref{sec_SGD_sc:notation_K*} we have for all $k\geq {\cal K}^*$
\begin{align*}
& - \frac{\sigma }{4}\mathbb{E}[\|x_{k}-x^*\|^2]   + (50M^2+2)\alpha_{k;\tau(\alpha_{k})}\mathbb{E}\left[\|x_{k}-x^*\|^2\right]  \leq 0.\\
&k\alpha_{k;\tau(\alpha_{k})}\leq k\tau(\alpha_{k})\alpha_{k-\tau(\alpha_{k})} = \frac{4k\tau(\alpha_{k})}{\sigma(k-\tau(\alpha_{k}))}\leq \frac{8\tau(\alpha_{k})}{\sigma}\cdot
\end{align*}
Thus, summing up both sides of \eqref{sec_SGD_sc:thm_rate:eq1} over $k$ and using the preceding three relations we have $\forall k\geq {\cal K}^{*}$
\begin{align*}
0&\leq \frac{\sigma {\cal K}^{*}({\cal K}^{*}-2)}{8} \mathbb{E}[\|x_{{\cal K}^{*}}-x^*\|^2] - \frac{\sigma k^2}{8}\mathbb{E}[\|x_{k+1}-x^*\|^2] + \frac{40(15M^2+1)}{\sigma}
\sum_{t={\cal K}^{*}}^{k}\ln\left(\frac{\sigma t}{4}\right)\notag\\
&\leq \frac{\sigma {\cal K}^{*}({\cal K}^{*}-2)}{8} \mathbb{E}[\|x_{{\cal K}^{*}}-x^*\|^2] - \frac{\sigma k^2}{8}\mathbb{E}[\|x_{k+1}-x^*\|^2] + \frac{40(15M^2+1)\log(\sigma k/4)}{\sigma k},
\end{align*}
which implies \eqref{sec_SGD_sc:thm_rate:ineq}, i.e., for all $k\geq {\cal K}^{*}$
\begin{align*}
\mathbb{E}[\|x_{k+1}-x^*\|^2]\leq \frac{{\cal K}^{*}({\cal K}^{*}-2)}{k^2}\mathbb{E}[\|x_{{\cal K}^{*}}-x^*\|^2] + \frac{320(15M^2+1)\log(\sigma k/4)}{k\sigma}\cdot
\end{align*}
\end{proof}

\subsection{Convergence analysis: smoothness and error bound conditions}\label{sec:SGD_eb}
In this section, we study the convergence rate of \eqref{sec_SGD:alg} when $f$ is a smooth convex function and satisfies the error bound condition. In particular, given a point $x$ we denote by $\hat{x}$ the projection of $x$ to ${\cal X}^*$, i.e.,
\begin{align}
\hat{x} = \arg\min_{y\in{\cal X}^*}\|x-y\|.
\end{align}
The error bound condition is then defined as below \cite{KarimiNS2016}.
\begin{assump}\label{assump:error_bound}
We assume that $\nabla f$ satisfies the following condition for all $x$
\begin{align}
\|\nabla f(x)\|_{*} \geq \sigma \|x-\hat{x}\|.\label{assump:error_bound:ineq}
\end{align}
\end{assump}
We note that this error bound condition is weaker than the strong convexity assumption in \eqref{assump_sc:ineq}, i.e., \eqref{assump_sc:ineq} implies \eqref{assump:error_bound:ineq}. This condition does not imply that $x^*$ is unique if it exists, i.e., if ${\cal X}^*$ is nonempty then it may contains more than one element. However, the convergence rate of the classic gradient descent under the this condition is the same as the one under strong convexity, that is, they both achieve a linear convergence rate \cite{KarimiNS2016,BolteNPS2017,LuoT1993,Zhang2017,Schopfer2016}. We derive the convergence rate of {\sf SGD} under Assumption \ref{assump:error_bound} in this section, which says that $x_{k}$ converges to $x^*$ in expectation at a rate
\begin{align}
\mathbb{E}\left[\|x_{k}-{\hat{x}}_{k}\|^2\right]  \lesssim {\cal O}\left(\frac{\mathbb{E}\left[\|x_{{\cal K}^*}-{\hat{x}}_{{\cal K}^*}\|^2\right]}{k^2} + \frac{\log(k)}{k}\right),
\end{align}
where ${\cal K}^*$ is a positive interger defined later. Basically, this result says that $x_{k}$ converges to the optimal set ${\cal X}^*$ in expectation. To achieve this result, we present some properties of \eqref{assump:error_bound:ineq} under the smooth condition of $f$ \cite{LuoT1993,BolteNPS2017,Zhang2017,KarimiNS2016,Schopfer2016}.
\begin{assump}\label{assump:smooth}
$f$ is continuously differentiable and there exists a constant $L>0$ such that
\begin{align}
    \|\nabla f(x) - \nabla f(y)\|_{*} \leq L\|x-y\| ,\qquad \forall x,y\in\mathbb{R}^{d}.    \label{assump_smooth:ineq}
\end{align}
\end{assump}
Under this assumption, the condition \eqref{assump:error_bound:ineq} implies the Polyak-Lojasiewicz ({\sf PL}) condition
\begin{align}
\frac{L}{2\sigma}\|\nabla f(x)\|_{*}^2 \geq f(x) - f^*,\label{assump:PL:ineq}
\end{align}
which can be derived from the following inequality using $\nabla f({\hat{x}}) = 0$
\begin{align}
f(x) - f^* = f(x)  - f(\hat{x}) \leq \frac{L}{2}\|x-\hat{x}\|^2 \leq \frac{L}{2\sigma}\|\nabla f(x)\|^2.\label{assump:PL:ineq1}
\end{align}
Second, the error bound condition also implies the following quadratic growth ({\sf QG}) condition \cite{KarimiNS2016,Schopfer2016}
\begin{align}
\frac{2\sigma}{L}\|x-{\hat{x}}\|^2\leq f(x) - f^*.    \label{assump:QG:ineq}
\end{align}
To derive this rate, we  consider the following two key lemmas. The first lemma is to provide an upper bound on the function value by using the Lipschitz continuity of the gradient of $f$.
\begin{lem}\label{sec_SGD_eb:lem_f_fk}
Suppose that Assumption \ref{assump:smooth} holds. Let $\{x_{k}\}$ be generated by \eqref{sec_SGD:alg}. Then we have
\begin{align}
f(x_{k+1}) &\leq f(x_{k}) -\alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)\|\nabla f(x_k)\|_{*}^2 -\alpha_{k}\left(1-L\alpha_{k}\right)\langle\nabla f(x_k), G(x_{k};\xi_{k})-\nabla f(x_k)\rangle\notag\\
&\qquad + 4M^2L\alpha_{k}^2\|x_{k}\|^2 + 4M^2L\alpha_{k}^2.\label{sec_SGD_eb:lem_f_fk:Ineq}
\end{align}
\end{lem}

\begin{proof}
By \eqref{assump_smooth:ineq} we have
\begin{align}
f(x_{k+1}) &\leq f(x_k) + \langle\nabla f(x_k), x_{k+1} -x_{k}\rangle + \frac{L}{2}\|x_{k+1}-x_{k}\|^2\notag\\
&= f(x_k) - \alpha_{k}\langle\nabla f(x_k), G(x_{k};\xi_{k})\rangle + \frac{L\alpha_{k}^2}{2}\|G(x_{k};\xi_{k})\|_{*}^2\notag\\
&= f(x_k) - \alpha_{k}\|\nabla f(x_k)\|_{*}^2 - \alpha_{k}\langle\nabla f(x_k), G(x_{k};\xi_{k})-\nabla f(x_k)\rangle\notag\\
&\qquad + \frac{L\alpha_{k}^2}{2}\|\nabla f(x_{k})\|_{*}^2 + L\alpha_{k}^2\langle\nabla f(x_k), G(x_{k};\xi_{k})-\nabla f(x_k)\rangle + \frac{L\alpha_{k}^2}{2}\|G(x_{k};\xi_{k})-\nabla f(x_{k})\|_{*}^2 \notag\\
&= f(x_{k}) -\alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)\|\nabla f(x_k)\|_{*}^2 -\alpha_{k}\left(1-L\alpha_{k}\right)\langle\nabla f(x_k), G(x_{k};\xi_{k})-\nabla f(x_k)\rangle\notag\\
&\qquad + \frac{L\alpha_{k}^2}{2}\|G(x_{k};\xi_{k})-\nabla f(x_{k})\|_{*}^2. \label{sec_SGD_eb:lem_f_fk:eq1}
\end{align}
By \eqref{assump:Lipschitz_sample:ineq} we have
\begin{align*}
\|G(x_{k};\xi_{k})-\nabla f(x_{k})\|_{*}^2 &\leq 2(\|G(x_{k};\xi_{k})\|_{*}^2 + \|\nabla f(x_{k})\|_{*}^2)\leq 8M^2(\|x_{k}\|^2+1).
\end{align*}
which when substituting into \eqref{sec_SGD_eb:lem_f_fk:eq1} yields \eqref{sec_SGD_eb:lem_f_fk:Ineq}.
\end{proof}
We next analyse the third term on the right-hand side of \eqref{sec_SGD_eb:lem_f_fk:Ineq}.
\begin{lem}\label{sec_SGD_eb:lem_bias}
Suppose that Assumptions \ref{assump:stationary}, \ref{assump:mix}, and \ref{assump:Lipschitz_sample} hold. Let $\{x_{k}\}$ be generated by \eqref{sec_SGD:alg}. Then  $\forall x\in{\cal X}$
\begin{align}
\mathbb{E}\left[-\langle\nabla f(x_k), G(x_{k};\xi_{k})-\nabla f(x_k)\rangle\right]\leq M(24ML\alpha_{k;\tau(\alpha_{k})}+\alpha_{k})\mathbb{E}\left[\|x_{k}\|^2\right] + 4M(\alpha_{k}+6ML\alpha_{k;\tau(\alpha_{k})}). \label{sec_SGD_eb:lem_bias:ineq}
\end{align}
\end{lem}

\begin{proof}
Consider
\begin{align}
&-\langle\nabla f(x_k), G(x_{k};\xi_{k})-\nabla f(x_k)\rangle\notag\\
&= \langle\nabla f(x_k) - \nabla f(x_{k-\tau(\alpha_{k})}), \nabla f(x_k) - G(x_{k};\xi_{k})\rangle + \langle\nabla f(x_{k-\tau(\alpha_{k})}), \nabla f(x_k) - G(x_{k};\xi_{k})\rangle.\label{sec_SGD_eb:lem_bias:eq1}
\end{align}
First, using \eqref{assump:mix} we have
\begin{align}
&\mathbb{E}\left[\langle\nabla f(x_{k-\tau(\alpha_{k})}), \nabla f(x_k) - G(x_{k};\xi_{k})\rangle\,|\,{\cal F}_{k-\tau(\alpha_{k})}\right]\notag\\
&=\langle\nabla f(x_{k-\tau(\alpha_{k})}), \mathbb{E}\left[\nabla f(x_k) - G(x_{k};\xi_{k})\rangle\,|\,{\cal F}_{k-\tau(\alpha_{k})}\right] \leq \alpha_{k}\|\nabla f(x_{k-\tau(\alpha_{k})})\|\notag\\
&\stackrel{\eqref{assump:Lipschitz_sample:ineq}}{\leq} M\alpha_{k}(\|x_{k-\tau(\alpha_{k})}\| + 1)\stackrel{\eqref{sec_SGD_sc:lem_xk_bounded_ineq2}}{\leq} 2M\alpha_{k}\|x_{k}\| + 3M\alpha_{k}\leq M\alpha_{k}\|x_{k}\|^2 + 4M\alpha_{k}.\label{sec_SGD_eb:lem_bias:eq1a}
\end{align}
Second, using \eqref{assump:Lipschitz_sample:ineq}, \eqref{sec_SGD_sc:lem_xk_bounded_ineq2}, \eqref{assump_smooth:ineq}, and \eqref{assump_smooth:ineq} we obtain
\begin{align}
&\langle\nabla f(x_k) - \nabla f(x_{k-\tau(\alpha_{k})}), \nabla f(x_k) - G(x_{k};\xi_{k})\rangle \leq L\|x_{k}-x_{k-\tau(\alpha_{k})}\|\left(\|\nabla f(x_k)\| + \|G(x_{k};\xi_{k})\|\right)\notag\\
&\stackrel{\eqref{sec_SGD_sc:lem_xk_bounded_ineq2}}{\leq} 2ML(\|x_{k}\| + 1)\left(6M\alpha_{k;\tau(\alpha_{k})}\|x_{k}\| + 6M\alpha_{k;\tau(\alpha_{k})}\right)\leq 24M^2L\alpha_{k;\tau(\alpha_{k})}\|x_{k}\|^2 + 24M^2L\alpha_{k;\tau(\alpha_{k})}.\label{sec_SGD_eb:lem_bias:eq1b}
\end{align}
Taking the expectation on both sides of \eqref{sec_SGD_eb:lem_bias:eq1} and using \eqref{sec_SGD_eb:lem_bias:eq1a} and \eqref{sec_SGD_eb:lem_bias:eq1b} yields \eqref{sec_SGD_eb:lem_bias:ineq}.
\end{proof}
We now present the main result in this section, which is the convergence rate of ${x_{k}}$ in expectation under Assumption \ref{assump:error_bound}.  First, we consider the choice of step sizes $\alpha_{k}$ as
\begin{align}
\alpha_{k} = \frac{\alpha_{0}}{k},\qquad \text{where }     \alpha_{0} = \min\left\{\frac{1}{2L};\,\frac{2L}{\sigma}\right\}.\label{sec_SGD_eb:stepsizes}
\end{align}
Moreover, with some abuse of notation, we consider in this section  ${\cal K}^*$ satisfying
\begin{align}
\left\{\begin{array}{l}
\tau(\alpha_{k})\alpha_{k-\tau(\alpha_{k})}\leq \max\left\{\frac{\log(2)}{M},\;\frac{\sigma}{L\sigma + 4M + 104M^2L}\right\}\\
\ln\left(\frac{k}{\alpha_{0}}\right)\leq \frac{k}{2}
\end{array}\right.\qquad \forall k \geq {\cal K}^*,   \label{sec_SGD_eb:notation_K*}
\end{align}
which also satisfies \eqref{sec_SGD:notation_K*}. The main result in this section is stated in the following theorem.

\begin{thm}\label{sec_SGD_eb:thm}
Suppose that Assumptions \ref{assump:optimal_set}--\ref{assump:Lipschitz_sample}, \ref{assump:error_bound}, \ref{assump:smooth} hold. Let $\{x_{k}\}$ be generated by \eqref{sec_SGD:alg}. In addition, let $\alpha_{k}$ satisfy \eqref{sec_SGD_eb:stepsizes} and  ${\cal K}^*$ be defined in \eqref{sec_SGD_eb:notation_K*}. We denote by $D_{1}$ and $D_{2}$ two constants as
\begin{align}
    \begin{aligned}
D_{1} &= 4M^2L + 4M + (2M + 8M^2L)\max_{x\in{\cal X}^*}\|x\|^2\\
D_{2} &= 24M^2L + 48M^2L\max_{x\in{\cal X}^*}\|x\|^2.
    \end{aligned}\label{sec_SGD_eb:thm:constants}
\end{align}
Then we have for all $k\geq{\cal K}^*$
\begin{align}
\mathbb{E}\left[\|x_{k+1} - {\hat{x}}_{k+1}\|^2\right] \leq \frac{L^2({\cal K}^*-1)^2\mathbb{E}\left[\|x_{{\cal K}^*}-{\hat{x}}_{{\cal K}^*}\|^2\right]}{4\sigma k^2}   + \frac{L\alpha_{0}^2D_{1}}{2\sigma k} + \frac{L\alpha_{0}D_{2}\ln\left(\frac{k}{\alpha_{0}}\right)}{\sigma k},\label{sec_SGD_eb:thm:ineq}
\end{align}
where recall that ${\hat{x}}_{k}$ is the projection of $x_{k}$ to ${\cal X}^*$.
\end{thm}

\begin{proof}
By \eqref{sec_SGD_eb:stepsizes} we have $(1-L\alpha_{k})\in(0,1)$. Taking the expectation on both sides of \eqref{sec_SGD_eb:lem_f_fk:Ineq} and using \eqref{sec_SGD_eb:lem_bias:ineq} we obtain
\begin{align*}
\mathbb{E}\left[f(x_{k+1})\right] &\leq \mathbb{E}\left[f(x_{k})\right] -\alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)\mathbb{E}\left[\|\nabla f(x_k)\|_{*}^2\right] +M\alpha_{k}\left(1-L\alpha_{k}\right)(24ML\alpha_{k;\tau(\alpha_{k})}+\alpha_{k})\mathbb{E}\left[\|x_{k}\|^2\right] \notag\\
&\qquad + 4M\alpha_{k}\left(1-L\alpha_{k}\right)(\alpha_{k}+6ML\alpha_{k;\tau(\alpha_{k})}) + 4M^2L\alpha_{k}^2\|x_{k}\|^2 + 4M^2L\alpha_{k}^2\notag\\
&\stackrel{\eqref{assump:error_bound:ineq}}{\leq} \mathbb{E}\left[f(x_{k})\right] -\sigma\alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)\mathbb{E}\left[\|x_{k}-{\hat{x}}_{k}\|^2\right] + 4M(ML+1)\alpha_{k}^2 + 24M^2L\alpha_{k;\tau(\alpha_{k})}\alpha_{k} \notag\\
&\qquad + M(1+4ML)\alpha_{k}^2 \mathbb{E}\left[\|x_{k}\|^2\right] + 24M^2L\alpha_{k;\tau(\alpha_{k})}\alpha_{k}\mathbb{E}\left[\|x_{k}\|^2\right],
\end{align*}
which by using the Cauchy-Schwarz inequality $\|x+y\|^2 \leq 2\|x\|^2 + 2\|y\|^2$ gives
\begin{align}
\mathbb{E}\left[f(x_{k+1})\right]
&\leq \mathbb{E}\left[f(x_{k})\right] -\sigma\alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)\mathbb{E}\left[\|x_{k}-{\hat{x}}_{k}\|^2\right] + 4M(ML+1)\alpha_{k}^2 + 24M^2L\alpha_{k;\tau(\alpha_{k})}\alpha_{k} \notag\\
&\qquad + 2M(1+4ML)\alpha_{k}^2 \mathbb{E}\left[\|x_{k}-{\hat{x}}_{k}\|^2\right] + 48M^2L\alpha_{k;\tau(\alpha_{k})}\alpha_{k}\mathbb{E}\left[\|x_{k}-{\hat{x}}_{k}\|^2\right]\notag\\
&\qquad + 2M(1+4ML)\alpha_{k}^2 \mathbb{E}\left[\|{\hat{x}}_{k}\|^2\right] + 48M^2L\alpha_{k;\tau(\alpha_{k})}\alpha_{k}\mathbb{E}\left[\|{\hat{x}}_{k}\|^2\right]\notag\\
&\leq \mathbb{E}\left[f(x_{k})\right] -\sigma\alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)\mathbb{E}\left[\|x_{k}-{\hat{x}}_{k}\|^2\right] + D_{1}\alpha_{k}^2 + D_{2}\alpha_{k;\tau(\alpha_{k})}\alpha_{k} \notag\\
&\qquad + 2M(1+4ML)\alpha_{k}^2 \mathbb{E}\left[\|x_{k}-{\hat{x}}_{k}\|^2\right] + 48M^2L\alpha_{k;\tau(\alpha_{k})}\alpha_{k}\mathbb{E}\left[\|x_{k}-{\hat{x}}_{k}\|^2\right].\label{sec_SGD_eb:thm:eq1}
\end{align}
where $D_{1}$ and $D_{2}$ are defined in \eqref{sec_SGD_eb:thm:constants}. By \eqref{sec_SGD_eb:notation_K*} we have for all $k\geq{\cal K}^*$
\begin{align*}
\left(\frac{L\sigma}{2} + 2M(1+4ML)\right)\alpha_{k} + 48M^2L \tau(\alpha_{k})\alpha_{k-\tau(\alpha_{k})}\leq \frac{L\sigma + 4M + 104M^2L}{2}\tau(\alpha_{k})\alpha_{k-\tau(\alpha_{k})} \leq \frac{\sigma}{2}.
\end{align*}
Then by \eqref{sec_SGD_eb:thm:eq1} we have for all $k\geq{\cal K}^*$
\begin{align*}
\mathbb{E}\left[f(x_{k+1})\right]
&\leq \mathbb{E}\left[f(x_{k})\right] -\frac{\sigma}{2}\alpha_{k}\mathbb{E}\left[\|x_{k}-{\hat{x}}_{k}\|^2\right] + D_{1}\alpha_{k}^2 + D_{2}\alpha_{k;\tau(\alpha_{k})}\alpha_{k},
\end{align*}
which by substracting both sides by $f^*$ and using \eqref{assump:PL:ineq} yields
\begin{align}
\mathbb{E}\left[f(x_{k+1})\right] - f^*
&\leq \mathbb{E}\left[f(x_{k})\right] - f^* -\frac{\sigma}{L}\alpha_{k}\left(\mathbb{E}\left[f(x_{k})\right] - f^*\right) + D_{1}\alpha_{k}^2 + D_{2}\alpha_{k;\tau(\alpha_{k})}\alpha_{k}\notag\\
&= \left(1-\frac{\sigma}{L}\alpha_{k}\right)\left(\mathbb{E}\left[f(x_{k})\right] - f^*\right) + D_{1}\alpha_{k}^2 + D_{2}\alpha_{k;\tau(\alpha_{k})}\alpha_{k}.\label{sec_SGD_eb:thm:eq1a}
\end{align}
Using the choice of step sizes in \eqref{sec_SGD_eb:stepsizes} we have
\begin{align*}
k^2 \left(1-\frac{\sigma}{L}\alpha_{k}\right) = k^2 \left(1-\frac{\sigma}{L}\frac{\alpha_{0}}{k}\right) \leq  k^2\left(1-\frac{2}{k}\right)\leq (k-1)^2.
\end{align*}
In addition, by \eqref{sec_SGD_eb:notation_K*} we also have
\begin{align*}
k\alpha_{k;\tau(\alpha_{k})} \leq \frac{\alpha_{0}k\tau(\alpha_{k})}{k-\tau(\alpha_{k})}\leq 2\alpha_{0}\tau(\alpha_{k}) = 2\alpha_{0}\ln\left(\frac{k}{\alpha_{0}}\right)
\end{align*}
Thus, by multiplying both sides of \eqref{sec_SGD_eb:thm:eq1} by $k^2$ and using the preceding two relations we obtain for all $k\geq{\cal K}^*$
\begin{align*}
k^2\left(\mathbb{E}\left[f(x_{k+1})\right] - f^*\right) &\leq (k-1)^2 \left(\mathbb{E}\left[f(x_{k})\right] - f^*\right) + \alpha_{0}^2D_{1} + 2\alpha_{0}D_{2}\ln\left(\frac{\alpha_{0}}{k}\right)\notag\\
&\leq ({\cal K}^*-1)^2 \left(\mathbb{E}\left[f(x_{{\cal K}^*})\right]- f^*\right)  + (k-{\cal K}^*) \alpha_{0}^2D_{1}  + 2\alpha_{0}D_{2}\sum_{t={\cal K}^*}^{k-1}\ln\left(\frac{t}{\alpha_{0}}\right)\notag\\
&\stackrel{\eqref{assump:PL:ineq1}}{\leq} \frac{L({\cal K}^*-1)^2\mathbb{E}\left[\|x_{{\cal K}^*}-{\hat{x}}_{{\cal K}^*}\|^2\right]}{2}   + k\alpha_{0}^2D_{1} + 2\alpha_{0}D_{2}k\ln\left(\frac{k}{\alpha_{0}}\right),
\end{align*}
which by using \eqref{assump:QG:ineq} and multiplying both sides by $L/2\sigma k^2$ gives us \eqref{sec_SGD_eb:thm:ineq}.
\end{proof}

\subsection{Convergence analysis: smoothness and nonconvexity}\label{sec:SGD_nc}
In this section, we study the convergence rate of \eqref{sec_SGD:alg} when $f$ is a smooth nonconvex function, i.e., $f$ satisfies Assumption \ref{assump:smooth}. In particular, we study the convergence to a stationary point of \eqref{sec_optimization:prob} in expectation, which happens at a rate
\begin{align*}
\mathbb{E}\left[\|\nabla f(x_R)\|_{*}^2\right]
\leq {\cal O}\left(\frac{\mathbb{E}\left[\|x_{{\cal K}^*} - {\hat{x}}_{{\cal K}^*}\|^2\right]}{\sqrt{T}}\right) + {\cal O}\left(\frac{\ln^2(T)}{\sqrt{T}}\right),
\end{align*}
where $T$ is some predetermined positive integer, and $x_{R}$ is randomly selected from the sequence $\{x_{k}\}$, for $k\in[{\cal K}^*,T]$,  with some probability. This random rule of choosing the return point $x_{R}$ is adopted from \cite{GhadimiL2013} for nonconvex optimization problems.

We now proceed to show our main result in this section. Given a positive integer $T$, consider the following choice of step sizes
\begin{align}
\alpha_{k} = \frac{\alpha_{0}}{\sqrt{k}},\qquad \text{for all }k\in[1,T],     \label{sec_SGD_nc:stepsizes}
\end{align}
and $\alpha_{0}$ satisfies
\begin{align}
0< \alpha_{0} \leq \max\left\{\max_{k\in[1,T]}\left\{ \frac{\sqrt{k+1}-\sqrt{k}}{2M}\right\}; \frac{1}{L}\right\}\cdot     \label{sec_SGD_nc:stepsizes:alpha0}
\end{align}
Moreover, we denote by $\delta$
\begin{align}
    \delta = \max_{k\in[1,T]} \left\{\frac{\sqrt{k}+M\alpha_{0}}{\sqrt{k+1}}\right\}  \in (0,1).\label{sec_SGD_nc:notation_delta}
\end{align}
Finally, let ${\cal K}^*$ be a positive integer such that
\begin{align}
\tau(\alpha_{k})\alpha_{k-\tau(\alpha_{k})}\leq \frac{\log(2)}{M}\quad \text{and }\quad \ln\left(\frac{\sqrt{k}}{\alpha_{0}}\right)\leq \min\left\{\delta^{k/2},\;\frac{\alpha_{0}}{\sqrt{k}}\right\},\quad \forall k \geq {\cal K}^*.     \label{sec_SGD_nc:notation_K*}
\end{align}
Under these conditions, we next consider the following lemma, which provide upper bounds for the time $\alpha$-weighted average of the iterates generated by \eqref{sec_SGD:alg}.
\begin{lem}\label{sec_SGD_nc:lem_xk_bound}
Suppose that Assumption \ref{assump:Lipschitz_sample} holds. Let $\{x_{k}\}$ be generated by \eqref{sec_SGD:alg}. Given a positive integer $T\geq {\cal K}^*$, let $\alpha_{k}$ be chosen in \eqref{sec_SGD_nc:stepsizes}. Then we have for all $k\in [{\cal K}^*,T]$
\begin{align}
&\sum_{k={\cal K}^*}^{T}\alpha_{k}^2\|x_{k}\|^2 \leq D_{3} \triangleq  \frac{3\alpha_{0}^2}{1-\delta^2} + \frac{3M^2\alpha_{0}^4}{(1-\delta)^3} + \frac{24 M^2\alpha_{0}^2}{(1-\delta)^2}\cdot \label{sec_SGD_nc:lem_xk_bound:ineq1}\\
&\sum_{k={\cal K}^*}^{T}  \alpha_{k;\tau(\alpha_{k})}\alpha_{k}\|x_{k}\|^{2}\leq D_{4}\triangleq  \frac{3\sqrt{2}\alpha_{0}^2}{1-\delta} + \frac{3\sqrt{2}M^2\alpha_{0}^4}{(1-\delta)(1-\sqrt{\delta})} + \frac{24\sqrt{2} M^2\alpha_{0}^2}{(1-\delta)^2}\cdot\label{sec_SGD_nc:lem_xk_bound:ineq2}
\end{align}
\end{lem}

\begin{proof}
Using \eqref{sec_SGD_sc:lem_xk_bounded_Eq1a}, $\alpha_{k} = \alpha_{0}/\sqrt{k}$, and \eqref{sec_SGD_nc:notation_delta} we have for all $k\geq [{\cal K}^*,T]$
\begin{align*}
\alpha_{k+1}\|x_{k+1}\| &\leq \alpha_{k+1}(1+M\alpha_{k})\|x_{k}\| + M\alpha_{k}\alpha_{k+1} = \left(\frac{\sqrt{k}+M\alpha_{0}}{\sqrt{k+1}}\right)\alpha_{k}\|x_{k}\| + M\alpha_{k}\alpha_{k+1}\notag\\
&\leq \delta\alpha_{k}\|x_{k}\| + M\alpha_{k}\alpha_{k+1} \leq \delta^{k}\alpha_{0}\|x_{1}\| + M\sum_{t=1}^{k}\alpha_{k}^2\delta^{k-t}\notag\\
&= \delta^{k}\alpha_{0}\|x_{1}\| + M\sum_{t=1}^{\lfloor k/2 \rfloor}\alpha_{k}^2\delta^{k-t} + M\sum_{t=\lceil k/2\rceil}^{k}\alpha_{k}^2\delta^{k-t}\notag\\
&\leq \delta^{k}\alpha_{0}\|x_{1}\| + M\alpha_{0}^2\sum_{t=1}^{\lfloor k/2 \rfloor}\delta^{k-t} + M\alpha_{\lceil k/2\rceil}^2\sum_{t=\lceil k/2\rceil}^{k}\delta^{k-t}\notag\\
&\leq \delta^{k}\alpha_{0}\|x_{1}\| + \frac{M\alpha_{0}^2}{1-\delta}\delta^{\lceil k/2\rceil} + \frac{M}{1-\delta}\alpha_{\lceil k/2\rceil}^2,
\end{align*}
which using the Cauchy-Schwarz inequality gives
\begin{align*}
\alpha_{k+1}^2\|x_{k+1}\|^{2}\leq 3\alpha_{0}^2\|x_{1}\|^2\delta^{2k} + \frac{3M^2\alpha_{0}^{4}}{(1-\delta)^2}\delta^{k+1} + \frac{12 M^2\alpha_{0}^2}{(1-\delta)^2}\frac{1}{k^2}\cdot
\end{align*}
Summing up both sides from $k = {\cal K}^*,\ldots,T$ yields \eqref{sec_SGD_nc:lem_xk_bound:ineq1}
\begin{align*}
\sum_{k={\cal K}^*}^{T}\alpha_{k}^2\|x_{k}\|^2 &\leq   \sum_{k={\cal K}^*}^{T} 3\alpha_{0}^2\|x_{1}\|^2\delta^{2k} + \sum_{k={\cal K}^*}^{T} \frac{3M^2\alpha_{0}^{4}}{(1-\delta)^2}\delta^{k+1}  + \sum_{k={\cal K}^*}^{T} \frac{12 M^2\alpha_{0}^2}{(1-\delta)^2}\frac{1}{k^2} \notag\\
&\leq \frac{3\alpha_{0}^2}{1-\delta^2} + \frac{3M^2\alpha_{0}^4}{(1-\delta)^3} + \frac{24 M^2\alpha_{0}^2}{(1-\delta)^2}\cdot
\end{align*}
Similarly, we consider
\begin{align*}
&\alpha_{k+1;\tau(\alpha_{k+1})}\alpha_{k+1}\|x_{k+1}\|^{2}\leq \frac{\alpha_{k+1;\tau(\alpha_{k+1})}}{\alpha_{k+1}}\alpha_{k+1}^2\|x_{k+1}\|^{2}\leq \frac{\tau(\alpha_{k+1})\alpha_{k+1-\tau(\alpha_{k+1})}}{\alpha_{k+1}}\alpha_{k+1}^2\|x_{k+1}\|^{2}\notag\\
&= \frac{\tau(\alpha_{k+1})\sqrt{k+1}}{\sqrt{k+1-\tau(\alpha_{k+1})}}\alpha_{k+1}^2\|x_{k+1}\|^{2}\leq \sqrt{2}\tau(\alpha_{k+1})\alpha_{k+1}^2\|x_{k+1}\|^{2},
\end{align*}
which by using \eqref{sec_SGD_nc:notation_K*} gives \eqref{sec_SGD_nc:lem_xk_bound:ineq2}
\begin{align*}
&\sum_{k={\cal K}^*}^{T}  \alpha_{k;\tau(\alpha_{k})}\alpha_{k}\|x_{k}\|^{2}\leq  \sqrt{2}\sum_{k={\cal K}^*}^{T}  \tau(\alpha_{k})\alpha_{k}^2\|x_{k}\|^{2}\notag\\
&\leq \sum_{k={\cal K}^*}^{T} 3\sqrt{2}\alpha_{0}^2\|x_{1}\|^2\delta^{k} + \sum_{k={\cal K}^*}^{T} \frac{3M^2\alpha_{0}^{4}}{(1-\delta)^2}\delta^{k/2}  + \sum_{k={\cal K}^*}^{T} \frac{12 M^2\alpha_{0}^2}{(1-\delta)^2}\frac{1}{k^{3/2}}\notag\\
&\leq  \frac{3\sqrt{2}\alpha_{0}^2}{1-\delta} + \frac{3\sqrt{2}M^2\alpha_{0}^4}{(1-\delta)(1-\sqrt{\delta})} + \frac{24\sqrt{2} M^2\alpha_{0}^2}{(1-\delta)^2}\cdot
\end{align*}

\end{proof}

We now state the main result in this section, which is the rate of {\sf SGD} when $f$ is nonconvex and smooth. To do it, we adopt the randomized stopping rule in \cite{GhadimiL2013}, that is, given a sequence $\{x_{k}\}$ generated by {\sf SGD} we derive the convergence of $x_{R}$, a random point selected from this sequence. More detail is given in the following theorem.
\begin{thm}\label{sec_SGD_nc:thm_rate}
Suppose that Assumptions \ref{assump:stationary}-- \ref{assump:Lipschitz_sample}, and \ref{assump:smooth} hold. Let $\{x_{k}\}$ be generated by \eqref{sec_SGD:alg}. Given a positive integer $T\geq {\cal K}^*$, let $\alpha_{k}$ satisfies \eqref{sec_SGD_nc:stepsizes}.
In addition, we randomly select $x_{R}$ from the sequence $\{x_{k}\}$, for $k\in[{\cal K}^*,T]$, with probability $P_{R}(\cdot)$ defined as
\begin{align}
P_{R}(k) = \mathbb{P}(R=k) = \frac{2\alpha_{k}-L\alpha_{k}^2}{\sum_{k={\cal K}^*}^{T}(2\alpha_{k}-L\alpha_{k}^2)}\cdot     \label{sec_SGD_nc:thm_rate:P_R}
\end{align}
Then we have
\begin{align}
\mathbb{E}\left[\|\nabla f(x_R)\|_{*}^2\right]
&\leq \frac{2L\mathbb{E}\left[\|x_{{\cal K}^*} - {\hat{x}}_{{\cal K}^*}\|^2\right] + 4D_{3}M(4ML+1) + 96D_{4}M^2L}{3\alpha_{0}\sqrt{T}}\notag\\
&\qquad  + \frac{ 4\alpha_{0}^2(1+\ln(T)) + 2\ln^2\left(\frac{T}{\alpha_{0}}\right)}{3\alpha_{0}\sqrt{T}},\label{sec_SGD_nc:thm_rate:ineq}
\end{align}
where recall that ${\hat{x}}$ is the projection of $x$ to the optimal set ${\cal X}^*$.
\end{thm}

\begin{proof}
Taking the expectation of  \eqref{sec_SGD_eb:lem_f_fk:Ineq} and using \eqref{sec_SGD_eb:lem_bias:ineq} we obtain
\begin{align*}
\mathbb{E}\left[f(x_{k+1})\right] &\leq \mathbb{E}\left[f(x_{k})\right] -\alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)\mathbb{E}\left[\|\nabla f(x_k)\|_{*}^2\right] + 4M^2L\alpha_{k}^2\mathbb{E}\left[\|x_{k}\|^2\right] + 4M^2L\alpha_{k}^2\notag\\
&\qquad + M\alpha_{k}\left(1-L\alpha_{k}\right)(24ML\alpha_{k;\tau(\alpha_{k})}+\alpha_{k})\mathbb{E}\left[\|x_{k}\|^2\right]\notag\\
&\qquad + 4M\alpha_{k}\left(1-L\alpha_{k}\right)(\alpha_{k}+6ML\alpha_{k;\tau(\alpha_{k})})\notag\\
&\leq \mathbb{E}\left[f(x_{k})\right] -\alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)\mathbb{E}\left[\|\nabla f(x_k)\|_{*}^2\right]  + 4M(ML+1)\alpha_{k}^2 + 24M^2L\alpha_{k;\tau(\alpha_{k})}\alpha_{k} \notag\\
&\qquad + M(4ML+1)\alpha_{k}^2\mathbb{E}\left[\|x_{k}\|^2\right] + 24M^2L\alpha_{k;\tau(\alpha_{k})}\alpha_{k}\mathbb{E}\left[\|x_{k}\|^2\right],
\end{align*}
which by summing up both sides over $k = {\cal K}^*,\ldots, T$ and reorganizing we obtain \begin{align}
&\sum_{k = {\cal K}^*}^{T}   \alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)\mathbb{E}\left[\|\nabla f(x_k)\|_{*}^2\right]\notag\\
&\leq \mathbb{E}\left[f(x_{{\cal K}^*}) - f(x_{T+1})\right]  + \sum_{k={\cal K}^*}^{T}\left(4M(ML+1)\alpha_{k}^2 + 24M^2L\alpha_{k;\tau(\alpha_{k})}\alpha_{k}\right)\notag\\
&\qquad + \sum_{k={\cal K}^*}^{T}\left[M(4ML+1)\alpha_{k}^2\mathbb{E}\left[\|x_{k}\|^2\right] + 24M^2L\alpha_{k;\tau(\alpha_{k})}\alpha_{k}\mathbb{E}\left[\|x_{k}\|^2\right]\right]\notag\\
&\leq \mathbb{E}\left[f(x_{{\cal K}^*}) - f^*\right]  + \sum_{k={\cal K}^*}^{T}\left(4M(ML+1)\alpha_{k}^2 + 24M^2L\alpha_{k;\tau(\alpha_{k})}\alpha_{k}\right)\notag\\
&\qquad + D_{3}M(4ML+1) + 24D_{4}M^2L,\label{sec_SGD_nc:thm_rate:Eq1}
\end{align}
where $D_{3}$ and $D_{4}$ are given in \eqref{sec_SGD_nc:lem_xk_bound:ineq1} and \eqref{sec_SGD_nc:lem_xk_bound:ineq2}, respectively. Note that, by \eqref{sec_SGD_nc:stepsizes} we have
\begin{align*}
&\sum_{k = {\cal K}^*}^{T}   \alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)\geq \frac{3}{4}\sum_{k = {\cal K}^*}^{T}   \alpha_{k} = \frac{3}{4}\sum_{k = {\cal K}^*}^{T}\frac{\alpha_{0}}{\sqrt{k}} \geq \frac{3\alpha_{0}\sqrt{T}}{4}\cdot\notag\\
&\sum_{k={\cal K}^*}^{T}\alpha_{k}^2 = \sum_{k={\cal K}^*}^{T}\frac{\alpha_{0}^2}{k}\leq \alpha_{0}^2(1+\ln(T)).\notag\\
&\sum_{k={\cal K}^*}^{T}\alpha_{k;\tau(\alpha_{k})}\alpha_{k}\leq \sum_{k={\cal K}^*}^{T}\frac{\alpha_{0}^2\ln(\tau(\alpha_{k}))}{\sqrt{k}\sqrt{k-\ln(\tau(\alpha_{k}))}}\leq \sum_{k={\cal K}^*}^{T}\frac{2\alpha_{0}^2\ln(\tau(\alpha_{k}))}{k}\leq \frac{\ln^2\left(\frac{T}{\alpha_{0}}\right)}{2}\cdot
\end{align*}
Diving both sides of \eqref{sec_SGD_nc:thm_rate:Eq1} by $\sum_{k = {\cal K}^*}^{T}   \alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)$ and using the preceding three relations yield
\begin{align*}
&\frac{\sum_{k = {\cal K}^*}^{T}  \alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)\mathbb{E}\left[\|\nabla f(x_k)\|_{*}^2\right]}{\sum_{k = {\cal K}^*}^{T}   \alpha_{k}\left(1-\frac{L\alpha_{k}}{2}\right)}\notag\\
&\leq \frac{4\mathbb{E}\left[f(x_{{\cal K}^*}) - f^*\right] + 4D_{3}M(4ML+1) + 96D_{4}M^2L}{3\alpha_{0}\sqrt{T}} + \frac{ 4\alpha_{0}^2(1+\ln(T)) + 2\ln^2\left(\frac{T}{\alpha_{0}}\right)}{3\alpha_{0}\sqrt{T}}\notag\\
&\leq \frac{2L\mathbb{E}\left[\|x_{{\cal K}^*} - {\hat{x}}_{{\cal K}^*}\|^2\right] + 4D_{3}M(4ML+1) + 96D_{4}M^2L}{3\alpha_{0}\sqrt{T}} + \frac{ 4\alpha_{0}^2(1+\ln(T)) + 2\ln^2\left(\frac{T}{\alpha_{0}}\right)}{3\alpha_{0}\sqrt{T}},
\end{align*}
where the last inequlaity is due to the Lipschitz continuity of $\nabla f$. Using the definition of $x_{R}$ in \eqref{sec_SGD_nc:thm_rate:P_R} immediately yields \eqref{sec_SGD_nc:thm_rate:ineq}.
\end{proof}

redpajama_set_name: RedPajamaArXiv


text:
Saleh Abu Jamal
Arab bus driver attacked by Kiryat Arba settlers
Saleh Abu Jamal assaulted by Jewish youth while driving a bus from Jerusalem to the settlement; according to the driver, the youths swore at him, threatened him and hit him in the face; two suspects arrested, aged 19 and 21.
Hassan Shaalan|Published: 02.19.18 , 13:24
An Egged Ta'avura bus driver was attacked early Sunday morning while driving a bus from Jerusalem to Kiryat Arba.
Saleh Abu Jamal, 26, from Jabel Mukaber in east Jerusalem, suffered a head injury and was taken to the Shaare Zedek Medical Center in the capital for treatment.
"In his complaint, the driver said that around 5am, while driving an Egged night bus from Jerusalem to Kiryat Arba, several drunken youths began urging him to get to the settlement (faster). He explained that the weather conditions did not allow that, and they then started swearing at him and hit him in the face," police said.
"At the entrance to Kiryat Arba, (Abu Jamal) stopped the bus and was able to call the police center and report it after another passenger came to his aid and separated between him and the attackers. As a result of the assault, he was lightly bruised in his head and was taken to receive medical treatment. Police forces that arrived at the scene detained for questioning two youths (aged 19 and 21) residents of Kiryat Arba on suspicion of attacking the driver," police added.
Abu Jamal said the passengers began interrupting him during the drive. He asked them to stop, to no avail. "They started swearing at me, told me, 'Keep driving. You Arab, what are you doing here?' I told them to keep quiet, otherwise I wouldn't be able to continue the drive," he said.
"They ignored my request and continued cursing at me for no reason. I called the coordinator and informed him about settlers who were interrupting me. He asked that I go to the Egged parking lot, and that is where I went immediately upon arriving in the city," Abu Jamal recounted.
"As I was turning to head to the parking lot, the settlers told me, 'Where are you going? Keep driving, you have to take us where we want to go.' I told them I couldn't in a situation like this. At that moment, they took the bag that holds the money and several other things and started threatening me. One of them, who claimed he was a soldier, hit me in the head and bruised me. After that I stopped at the parking lot, and I was evacuated to the hospital from there," he said.
Abu Jamal claimed he did not tell the police his attackers were drunk. "I don't know why the police made such a claim. They were acting normally, not under the influence of alcohol. In my opinion, this is a racist act. The swearing and the threatening I experienced point to a racist act," he asserted.
"Now I'm afraid to go back to work on the same line. This time I was lightly wounded, but next time it could end in disaster," Abu Jamal concluded.
The police said its officers will "continue acting with zero tolerance and with determination against those who use violence against service providers and public employees. We will use any means at our disposal to catch the attackers and bring them to justice in order to protect the security and well-being of citizens."
Egged Ta'avura, a subsidiary of Egged, said, "This serious incident is another case in a long line of intolerable incidents in which bus drivers were attacked. We consider any use of violence against drivers to be very grave.
"We turned to the Kiryat Arba council and to law enforcement officials in the area in order to work together to eradicate this phenomenon. We trust the Israel Police and call on passengers to remember that if any complaint arises, they should turn to the company and not break the law."

redpajama_set_name: RedPajamaCommonCrawl


Watch this junior college baseball team get fooled by Cubs All-Star Kris Bryant in a prank set up by Red Bull.
There always seems to be a player who joins a team late or transfers from another squad and doesn't have to do the work, but still plays. The Mesa Community College baseball team recently found themselves in that situation—sort of.
Red Bull pulled a prank in which Chicago Cubs third baseman Kris Bryant pretended to be a transfer player from Europe, coming in to steal playing time from some of Mesa's starters. Even before Bryant (a.k.a. Roy) arrived, the athletes started worrying about their job security. As soon as the big league slugger showed up and started cranking out big hits, he had everyone's attention.
There always seems to be a player who joins a team late or transfers from another squad and doesn't have to do the work, but still plays. The Mesa Community College baseball team recently found themselves in that situation—sort of.
You can see it in these young ballplayers' eyes. They knew that "Roy" was something special. But it didn't take long for the Mesa players to realize something was amiss. The ruse was short-lived, and after a few thunderous cracks of the bat, Bryant's true identity was revealed.


Here's a little recap below from the CES show where Withings announced the product along with a video at the link.
"At CES in Las Vegas this week there were all kinds of new devices shown and some will make it and some won't but this one looks like a winner. You may have already read about the Withings blue tooth and WiFi Scale at the Quack and now they are adding on the Iphone/Ipad connection for taking your blood pressure.
I don't know about the blood pressure product but the scale uses 2D bar codes along with Google Health and Healthvault to insure privacy and I wrote about this a while back in March of last year.
In April of this year the FDA new rule came into play for MMDS medical devices with rules for Class 1 items. I said at that time if unsure, register and this applies to devices that transmit data and you can see blood pressure devices are right in here. The Class 1 rule is for devices that don't affect a patient's care, like an automated IV machine as an example that dispenses medications and reports data as that's a higher classification.
In addition there are other options available with using encrypted gateways to secure transmission of data with bar codes. Last week with all the hacking taking place, the post below with using "soft tokens" stored in a cell phone was very popular. Here's the video below showing how it works with HealthVault and again Withings is set up with 2D bar codes too for the scale.
I'm not sure if or when the blood pressure device from Withings will be connected but it could very well be on the way for secured connections. Using 2D bar codes are almost easier than making a phone call with your phone today. There are a couple more videos at the link above, and one directly speaks about Auth Tag and how a soft token could be the answer to carrying around a key fob for enterprise access to networks too. I would think that all types of agencies would be interested in this possibility and certainly one more item for the FDA to look at when clearing and registering MMDS (Medical Device Data Systems) with the new ruling in place. Here's the video on how the Withings Scale works below and the goal of HealthJibe is to connect more devices as they are approved to provide secure transmission of personal information.
Withings announced that the FDA has provided its iOS-powered blood pressure monitor with 510(k) clearance, and the company wasted little time making the device commercially available in the US. The FDA filed 510(k) clearance for the device about one month ago — on May 20, 2011 and the device went on sale over the weekend.


text:
7 Simple Steps To Loving Yourself During A Break Up
By Niña Terol, January 13th 2016
Yen Thu McGrath
1. Get moving.
I already knew early on that early in the year my ex and I would part ways. To prepare myself for this major life change, I decided to literally move in many areas of my life as well. I moved to a new job in a new city, moved to a new home that better suited my needs (and which was just walking distance to work), and physically moved as much as I could. I knew that losing weight had to be part of my transformation, so I walked whenever and wherever I could. I found that moving to a totally new environment — and moving my body regularly — gave me the physical and psychic (read: "of the psyche") boost to break my inertia, bring me the endorphins that I so badly needed, and energize me for the journey ahead.
2. Make new friends (and reconnect with old ones.)
And also engage in new activities. My move to a new job and a new city brought it with many good things: the opportunity to make new friends, reconnect with old ones, and try out new things that I previously didn't have the time or energy for. I enrolled in Zumba and yoga classes, started going out for weeknight drinks with new sets of friends, and (serendipitously) reconnected with old girlfriends who were undergoing a similar journey as I was. It helped to be surrounded by positive people with similar life goals, and it also helped to have friends with differing perspectives (who can knock some sense into your head when you need it).
3. Take better care of yourself.
At the time of the break-up, I was about 40 lbs. overweight for my height. I knew that I had to take better care of myself in order to look and feel my best, so I challenged myself to lose all the excess weight by shifting my lifestyle and without enrolling in expensive programs or fad diets. I focused on it, made myself a priority, and lost the 40 lbs. in just five months.
4. Speaking of the dating scene: get out there and meet new people.
When you're coming off an 11 year relationship and a five year marriage that didn't work out, it's easy to curse the rest of mankind and tell yourself that you'll never find love again. Instead of wallowing in self-pity and man-hating, I decided to use the opportunity to get to know other types of people and expand my own worldview. To me, coming off a marriage meant that I was not (and still not am) in a rush to get back into one, so there's really no pressure to "make something" out of a "connection". I told myself that I would only get back into a relationship "with the right guy, under the right timing and the right circumstances, and for the right reasons." For now, this phase is about getting to know other people — and discovering more about myself in the process.
5. Embrace your emotions and be true to yourself.
It will happen that you will start caring about someone else, and you will experience a range of emotions that will bring up old baggage and new fears. Acknowledge the feelings, own up to them, but don't allow yourself to be carried away. Remember: this is your phase to explore and discover, and you're not supposed to be rushing back into anything just yet. I will forever be grateful to the few good men whose paths intersected with mine during this very precarious stage of my life, yet never took advantage of my vulnerability. You prove that gentlemen still exist — and that real connections are possible through time, space, and time zones.
6. Be true to yourself no matter what.
Authenticity is a big part of what drives my journey, and I would rather be wrong than be a fake or a copycat. Over the past few months, I've discovered many facets of myself that are surfacing just now — and some of them aren't pretty. Instead of beating myself up over these, I've learned that it's better to just face myself squarely in the mirror, accept and embrace all of me, and learn from my mistakes and shortcomings. Nobody's perfect after all, but we can always strive to be better versions of ourselves every single day. The most important step here is giving ourselves permission to be who we truly are, making peace with that and loving it, yet still striving to be better as each day comes. If you won't accept and love yourself for who you truly are, nobody will.
7. Have a sense of humor.
There were so many moments during this six-month period that felt to me like one big movie — the script of which I was completely unaware of — when the Universe just chose to unleash its cosmic sense of humor and turn things completely upside-down for me. Another 'Remember': when these things happen, it's important to take a deep breath (or more), take a step back, and know that everything in life will pass — especially these little mishaps and misadventures. Yes, you're in pain; yes, this major life change is serious stuff; but, NO, the world doesn't owe you anything. You'll just have to roll with the punches and laugh things off as part of the adventure. You'll thank yourself for this attitude later on.
Niña Terol
Keep up with Niña on Twitter and ninasnotebook.com
Break ups Exes Getting Better Healing Inspirational Love Yourself Loving You Moving On Self-Care Self-Esteem Self-Love Writing and Expression
Here's What I Learned From 6 Months Of Couch Hopping
What Wearing A Tulle Skirt For A Day Taught Me About Self-Love
He Was 5'4″, I Was 5'10", And We Were in Love
All You Need To Do Is Give Yourself A Little Love
This Is How You Be A True Friend To Yourself


1. How straight did Barr play it?
The attorney general is one of the more mysterious figures in this story. On the one hand, he has experience in traditional Republican politics and a long friendship with Robert Mueller. On the other, his experience in Republican politics involves covering up a major presidential scandal, and he got his current role by writing a private memo attacking Mueller's obstruction investigation.
Seeing the full report would obviously go a long way toward resolving the question. In the meantime, the carefully parsed language in Barr's summary leaves plenty of room to question the underlying text.
2. What other obstruction of justice evidence is there?
But "most" does not mean "all." It could mean "basically everything," or it could mean "more than half." Other steps Trump may have taken to obstruct justice would be of high interest to Congress. One mystery: Did Mueller find additional evidence that Trump directed Michael Cohen to lie to Congress about Trump's efforts to get a building deal in Moscow during the campaign? BuzzFeed reported that he did, though the special counsel disputed the report. Cohen testified to Congress that Trump directed him to lie by repeating a false story before his testimony (the equivalent to saying "I was never here," or "We never had this conversation."). Did Mueller reach any conclusions?
Neal Katyal has argued that Mueller seemed to intend to leave the obstruction question for Congress to decide, as a political judgment. Instead, Barr imposed his own judgment. Only reading Mueller's own findings, and hearing his testimony, will answer this.
3. How much noncriminal collusion took place?
Barr states that Mueller "did not establish" that Trump engaged in a criminal conspiracy with Russia. There's no reason whatsoever to question that finding. And while that is an extremely important finding, it only answers one of the questions that propelled the investigation in the first place.
Before the report, I summarized the broad evidence of illicit contacts and corruption linking the Trump campaign with Russia. Rosalind Helderman and Natasha Bertrand have written excellent rundowns of many of the dangling threads that have been left from previous findings.
Who directed the senior official to contact Stone? (It could have been Trump himself.) To what extent was the Trump campaign coordinating with WikiLeaks to exploit the stolen emails?
Likewise, Manafort passed 75 pages of detailed polling information to a Russian agent. The matter went "very much to the heart of what the special counsel's office is investigating," prosecutor Andrew Weissmann told the court at the time.
Both Stone and Manafort withheld cooperation from Mueller, almost certainly banking on Trump delivering pardons. And Mueller clearly did not have enough evidence to prosecute Trump for any of their behavior. But that leaves a lot of room to establish what forms of noncriminal cooperation they were engaged in.
4. How much corruption took place?
Money was one of the key links between Trump and Russia. Corruption can be difficult to prove in court, but it's also perhaps the most important political question in the whole Russia scandal. To what extent did Trump have hidden financial interests that influenced his disposition toward Russia?
One of Russia's key political objectives in its support of Trump appears to have been lifting or softening sanctions that were imposed as a consequence of its invasion of Ukraine. That goal floats through several of the reported contacts — from the Trump Tower meeting to discuss adoptions (the Russian ban on American adoptions was in retaliation for the sanctions, and the two are essentially indistinguishable); to the August 2016 meeting between Manafort and Konstantin Kilimnik, which discussed sanctions; to Cohen's delivery to Michael Flynn of a Russia-friendly "peace plan" for Ukraine in early 2017.
Cohen testified that Trump was expecting a payday of several hundred-million dollars from the Moscow project. If true, this would not necessarily constitute a crime, but it is absolutely an open-and-shut case of corruption. Trump could not possibly formulate his Russia policy stance in good faith if he stood to gain such a gigantic windfall by staying in Vladimir Putin's good graces.
Trump has reportedly come to rely heavily on Russian financing in recent years. Mueller has reportedly seen Trump's tax returns, and Congress is also working to obtain them. Russia as a matter of practice spreads money around to its partners as a way of cultivating overseas influence. Has Mueller produced any additional evidence of financial links that could compromise Trump?
Corruption, like collusion, is not a crime. It can involve specific crimes that are difficult to prove in court (like bribery, which needs to demonstrate a quid pro quo.) But Congress obviously has a very strong interest in determining the level of corruption infecting Trump's relationship with Russia.
Ken Dilanian reports that the FBI is preparing a counterintelligence briefing to the Gang of Eight, the leaders of the House and Senate Intelligence Committees, in the next 30 to 60 days. That briefing apparently would address the real heart of the matter: Russian influence over Trump.


Read the full description below ?
A market leader… Siren Wellbeing Supplements for Women is formulated out of Shatavari and is utilised to help with a healthier menstrual period, assist in a tranquil changeover entering menopause, as well as support mothers while being pregnant, providing birth, and medical.
A trustworthy as well as, a healthful decision for women of various age groups, from children, mums & grandmums. Siren counterbalances a lady throughout her very own lifestyle.
This is our favourite Siren selection for ladies – produced to assist nurture and benefit you in each and every point in your daily life. Siren, have been working hard to improve and refine wellness vitamin supplements with your needs at heart.
The healthy balance as well as, regulation of hormonal periods underpins the female health and wellbeing. Furthermore regulating your monthly period, female fertility as well as the menopausal times, hormones can also be important in encouraging cell development and growth, combined with preserving a stable inner ecosystem.
Siren Wellbeing Supplements for Women, is an all natural Body hormone Balancer for females.
These tablets are ideal for Vegans.


text:
2010 Programming
This exhibition marks the first co-presentation between TSV and long-standing artist resource Vtape. As part of a curatorial development project, local emerging curator and artist Laura Paolini has organized an important historical exhibition on early forms of processed video images. The exhibition will occur at both TSV and Vtape.
This show opens a discussion of the paradoxes within this under-represented part of video art history. Working together, while remaining somewhat separate and outside the larger video art movement, and having close ties to experimental film as well as Fluxist and Dadaist art traditions, the work considered here is as subversive and potentially dark as it is precise or mathematical. Video art's early history tends to read as collective or activist driven and often as borderline utopic, using narrative and limited in-camera editing to create compelling works. These tendencies did exist within image processing circles, but this exhibition focuses on magnetic tape and non-narrative projects, pushing an aesthetic and political agenda, using video and audio synthesizers, tube based monitors and magnets to change and manipulate the tape.
Featuring work by: Kim Blain, Peer Bode, Jean Pierre Boyer, Barbara Buckner, Eric Siegel, Steina and Woody Vasulka, Jane Wright, and Nam June Paik and Jud Yalkut.
Organised by: Trinity Square Video & Vtape
Saturday, May 22, 2 – 5pm
Master Class with Steve Reinke
Sunday, May 23, 2 – 4pm
$25 TSV Members / $30 non-members
Trinity Square Video and Inside Out are pleased to present the North American premiere of the collaborative, editing and re-editing project, Disambiguation by the renowned artists Steve Reinke and James Richards. Working together remotely (Reinke in Chicago and Richards in London) with materials culled from each artist's extensive, idiosyncratic archive of found and personally recorded documents, Disambiguation is a hypnotic and beautiful "mix-tape" produced by two master editors. The artists' joint process of selection and revision recalls underground, bootlegged audio compilations–here, recontextualized by the ubiquity of digital video.
Steve Reinke is a Chicago-based artist and writer best known for his videos. His work is in many collections including the Museum of Modern Art (New York), the Centre Pompidou (Paris) and the National Gallery (Ottawa), and has screened at many festivals including Sundance, Rotterdam, Oberhausen and the New York Video Festival. Reinke received the Bell Canada Award in Video Art in 2006. In the 1990′s he produced The Hundred Videos (1996), an ambitious and highly influential video project, and a book of his scripts, Everybody Loves Nothing was published by Coach House (Toronto). He has also co-edited several books, including By the Skin of Their Tongues: Artist Video Scripts (co-edited with Nelson Henricks, 1997), Lux: A Decade of Artists' Film and Video (with Tom Taylor, 2000), and The Sharpest Point: Animation at the End of Cinema (with Chris Gehman, 2005). Reinke is associate professor of Art Theory & Practice at Northwestern University in Evanston, Illinois.
James Richards is an artist born in Wales (1983) and based in London. Richards has presented solo exhibitions at Tramway (Glasgow) and Swallow Street Gallery (London) and as part of the group shows Nought to Sixty at the ICA (London); Generational: Younger than Jesus at the New Museum (New York); and A Song For Those In Search Of What They Came With at Bellwether Gallery (New York). His single channel videos have been screened in curated programs at the Whitechapel Gallery (London), Light Industry (New York), and the Kölnischer Kunstverein (Cologne). Working as a curator, he has presented screenings at LUX (London), FormContent (London) and Light Industry (New York).
Please join us at TSV for a Master Class with Steve Reinke. Through specific reference to his own celebrated works, Reinke will discuss the implications and possibilities of editing and animating with Adobe After Effects.
All are welcome, but enrollment is limited.
To register please contact TSV by phone or email: [email protected]
Organised by: Trinity Square Video and Inside Out
Extra-Territoriality
The term "extra-territoriality" is a concept used to describe the state of exception of individuals and the (human) rights associated with citizenship to a region or land. Judiciously motivated by modern events, philosophic bio-political analysis has attempted to map the increasingly complex routes of sovereign power on the (bare) lives of individuals. But this mapping often foregoes an epilogue – all too often there is no afterward to describe the real existence of post-nation living and the reality of these lives as functioning, contemporary identities governed by dynamics historically enacted out of, and in spite of, the state of exception. Refugees and other extra-territorial persons, those who appear as the exception within an exception to the rule, are not some form of mythic, ironically liberated postmodern figures: the reality is that without citizenship, and the protection of the sovereignty that accompanies it, human rights can and will be violated and the democratic choices of the individual are annulled. Post-nation living, as vulnerable and volatile as it is, has created necessarily idiosyncratic processes of "citizenship" that are difficult to represent.
At the core of this issue is the ongoing question of whether or not right is necessarily associated with territory. The four works in this exhibition can all be organized and viewed in opposing pairs: the grounding in two physical places, Canada and Palestine; the perspective of the camera as an internal or external framing device; and the framework of discourse as a political analysis alongside a personal or allegorical one.
The mapping of this territory begins at the sea. In Sobhi al-Zobaidi's about the sea we hear the conversations of young Palestinian men and women as they lament the ongoing loss of their homeland through military occupation. Against this conversation, al-Zobaidi films the crashing waves on the beach and the open sea, a potent symbol of the ever-diminishing landscape within which this population resides. Moving from the waves of the Mediterranean to the expanses of central Canada, is Leah Decter's Imprint. Furthering this dialogue about location and migration, Decter's video is composed of a series of actions performed in the landscape which signifies the unmarking and remarking of territory. Through these performances, a narrative of personal and national histories and memories converge.
Moving further westward, and shifting perspectives from interior to exterior, Jayce Salloum's untitled part 4: terra incognita, looks at First Nations communities in and around Kelowna, BC. Interviewing various speakers of N'Syilx'cen (Okanagan), the video traces the history of European colonization in the region, and the tragic events to which their people were subject: biological warfare, residential schools, the reserve system, cultural decimation.
The exhibition closes with a return to Palestine in Ursula Biemann's video essay X-Mission, an analysis of the Palestinian refugees camps as a zone of exception. Biemann's ongoing practice in video has often been rooted in the investigation of borders, people, movement and nations, this video extending that conversation to the nationless, the extra-territorial. X-Mission explores this space through a legal, historical and symbolic engagement. The narrative, though focused on a Palestinian situation, frames the conversation on refugees within a broader diasporic context, questioning the idea of post-nationality.
Organised by: Ursula Biemann, Leah Decter, Jayce Salloum & Sobhi al-Zobaidi
ICON, VILLAIN, ANTIHERO
A trilogy of 15 commissioned works by 16 artists
including the compelling new works from
Trinity Square Video Themed Commission Program
New videos by Andrea Cooper, Kenneth Doren,
David Frankovich, Istvan Kantor and Tanya Read
ICON, VILLAIN, ANTIHERO Catalogue
Available for $5
Texts by Marusya Bociurkiw, Andrew James Paterson
and Mariko Tamaki, Illustrations by Willow Dawson
TSV's Themed Commission Trilogy, ICON, VILLAIN, ANTIHERO, concludes with the premiere of five compelling new videos created in response to the idea of the illusive figure of the antihero, and the launch of a gorgeous 50-page catalogue that profiles the entire trilogy.
The works in the ANTIHERO program explore the complexities of contemporary narrative characterization: Andrea Cooper's Tell Your Mother uses the haunting elisions of anachronism to study ambiguity in a "real" character; Kenneth Doren's Crap Days negotiates a complicated exchange between the familial and the foreign by using various UK football chants to charming–and malicious–effect; David Frankovich's Sweet Interlaced Transvestite reveals form as technological medium for the trans-mission of a message; Istvan Kantor's Song of the Anti-Hero employs the artist's renowned aplomb, wit and song to showcase the consumption–and replication–of the cinematic antihero; Tanya Read's Mr. Nobodyfeatures the artist's notorious animated character caught up in a never-ending digital desert.
TSV's Themed Commission Program offers selected artists the opportunity to make completely new work at TSV with full access to the centre's facilities for production, postproduction, education and dissemination.
The ICON, VILLAIN, ANTIHERO Catalogue celebrates the realization of this trilogy of Themed Commission Programs, a project which has provided sixteen fascinating videomakers–both emerging and established–the opportunity to explore ideas of persona, as inspired by classic characters in genre-fiction, often challenging deep-seated notions of screen-based performance and characterization through processes unique to artists' video.
Organised by: Trinity Square Video


Jim Reisman has been photographing Keshet Chaim for the past seven years. Many of the photographs on the site were taken by Jim.
Randy Bellous is an eleven-time award-winning television producer. Although his expertise is in live multi-camera television events, he has been producing network and cable television shows, live concert videos and elaborate corporate shows for over 18 years. His International credits include documentaries from The United Nations (Geneva, Switzerland), Live Showcase Stage Show Concerts from Yokohama, Japan, Carpi, Italy and the South Pacific World Music Festival in Savusavu, Fiji. His domestic credits include multiple NARAS "Live", Award Winning Events, Entertainment News, Daily Network television strips, commercials, U.S. Government Military Training Films and "Extreme" Sport shows.
David Kartsonis is a video producer and videographer among other skills. Kartsonis has shot and/or edited video for: Universal Studios, Disney, El Camino College, Shakespeare Festival/LA, LA Stage Alliance, WordTheatre, American City Business Journals, GuerilLA, Featured Chicken Films, Al Fresco Software, StoneBridge, Paperback Theater Company, Shrunken Head Productions, The Los Angeles Zoo, Bakers Man Productions and Keshet Chaim Dance Ensemble. For more about David visit www.bakersman.com.


text:
package com.folioreader.model.sqlite;

import android.content.ContentValues;
import android.content.Context;
import android.database.Cursor;
import android.database.sqlite.SQLiteDatabase;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * @author gautam chibde on 28/6/17.
 */

public class DictionaryTable {

    public static final String TABLE_NAME = "dictionary_table";

    public static final String ID = "_id";
    public static final String WORD = "word";
    public static final String MEANING = "meaning";
    private SQLiteDatabase database;

    public DictionaryTable(Context context) {
        FolioDatabaseHelper dbHelper = new FolioDatabaseHelper(context);
        database = dbHelper.getWritableDatabase();
    }

    public static final String SQL_CREATE = "CREATE TABLE IF NOT EXISTS " + TABLE_NAME + " ( " + ID
            + " INTEGER PRIMARY KEY AUTOINCREMENT" + ","
            + WORD + " TEXT" + ","
            + MEANING + " TEXT" + ")";

    public static final String SQL_DROP = "DROP TABLE IF EXISTS " + TABLE_NAME;

    public boolean insertWord(String word, String meaning) {
        ContentValues values = new ContentValues();
        values.put(WORD, word);
        values.put(MEANING, meaning);
        return database.insert(TABLE_NAME, null, values) > 0;
    }

    public void insert(Map<String, String> map) {
        database.beginTransaction();
        for (String key : map.keySet()) {
            insertWord(key.toLowerCase(), map.get(key));
        }
        database.setTransactionSuccessful();
        database.endTransaction();
    }

    public String getMeaningForWord(String word) {
        Cursor c = database.rawQuery("SELECT * FROM "
                + TABLE_NAME +
                " WHERE " + WORD + " = \"" + word.trim() + "\"", null);
        if (c.moveToFirst()) {
            String toRetuen = c.getString(2);
            c.close();
            return toRetuen;
        }
        c.close();
        return null;
    }

    public List<String> getMeaning(String word) {
        List<String> words = new ArrayList<>();
        String meaning = getMeaningForWord(word);
        if (meaning != null) {
            words.add(meaning);
            return words;
        } else {
            return getProbableCombinations(word);
        }
    }

    private List<String> getProbableCombinations(String word) {
        List<String> combinations = new ArrayList<>();
        for (int i = 1; i <= 3; i++) {
            String m = getMeaningForWord(word.substring(0, word.length() - i));
            if (m != null) {
                combinations.add(m);
            }
        }
        return combinations;
    }
}

redpajama_set_name: RedPajamaGithub


Macdonalds, Television Retaileres, listed under "Television Retaileres" category, is located at Carr Avenue Leiston Suffolk, IP16 4JA, United Kingdom and can be reached by 728830762 phone number. Macdonalds has currently 0 reviews.
Browse all Television Retaileres in Leiston Suffolk.


Founded in 1941, SAVE is an independent non-profit animal shelter dedicated to protecting the health and welfare of homeless companion animals in the greater Princeton area. Through six core programs of Rescue, Shelter, Health and Welfare, Spay/Neuter, Adoption, and Humane Education, SAVE focuses on the rehabilitation and successful placement of treatable and adoptable animals. SAVE endeavors to build, foster, and strengthen the human-animal bond.
On February 21, 2006, SAVE merged with Friends of Homeless Animals (FOHA). Founded in 1998, FOHA concentrated on animal rescue and care in the Princeton area. The new union, renaming the organization as SAVE, A Friend to Homeless Animals, is now the largest shelter for companion animals in the Princeton area. Consolidating 75 years of community involvement and a shared philosophy and mission, the merger of SAVE and FOHA has led to a greater number of successful adoptions.


The controller is available in one of two configurations: an in-line model which allows for direct installation of the probe and chemical injection fittings into existing piping (BL121-10) or a panel mounted system with a bypass flow cell (BL121-20). The bypass flow cell allows for calibration and maintenance of the probe without having to stop the recirculation pump.
The HI1036-1802 is a digital probe that measures pH, ORP, and temperature. This probe also incorporates a potential matching pin. The pin is considered the "earth ground" connection and is used to prevent ground loop effects from causing erratic readings and damage to the system.
The BL121 is equipped with two peristaltic dosing pumps with replaceable chemical resistant tubing. When using a diaphragm pump, chlorine gas formed from outgassing can collect in the pump head resulting in the pump losing its prime; the buildup of chlorine gas is not a problem with peristaltic pumps that use rollers and tubing.
The BL121 features proportionally controlled dosing pumps. Based on the sensitivity of the process to chemical addition, these controllers allow the user to adjust a proportional band. This setting determines the amount of time that the pumps are dosing as a percentage of the deviation from the set point allowing for very fine control in maintaining the desired set point.
The flow rate from the dosing pumps is adjustable from 0.5 to 3.5L/h. Larger bodies of water require more chemical to be dosed than small bodies since it takes more chemical to realize a change in the reading. The adjustable flow rate, like the proportional band, allows for better control in maintaining a desired set point.
With chlorine disinfection there is an inverse relationship between pH and ORP. As the pH level increases, the ORP level decreases. The BL121 utilizes a dosing consent feature that will not dose chlorine until the pH value is first corrected since it is possible to have a low ORP value even though there is sufficient chlorine. The dosing consent feature prevents wastage of chemicals and avoids a higher than necessary chlorine concentration.
An inline flow switch or a mechanical relay connected to the recirculation pump power source may be connected to the hold input of the BL121. With no flow or when no power is applied to the recirculation pump, the hold circuit disables the dosing pumps. This will prevent any dosing of chemical when there is no movement of water in the system.
The versatile display of the BL121 allows for three screen modes. The LCD can display all three parameters at one time, a 3-second cycle of single parameters, or a real-time plot screen with options for parameter selection, zooming, and log recall.
Hanna controllers allow users to enable or disable the low and high level of alarms for all parameters. When an alarm is activated, all dosing will stop. The alarm system also offers overdosing protection if the value is not corrected within a specified time interval then the meter will go into alarm status.
The BL121 offers multiple LED indicators for status, servicing, and pump operation. The STATUS LED changes color based on operational state; green when setting are in range, yellow when user intervention is required, and red for problems. The SERVICE LED indicates any alarms and process errors experienced by the controller.
The readings for each parameter are automatically logged every 10 seconds. A new log is started each time the instrument is calibrated or at the start of a new day. Logged data include pH, ORP, and temperature values, last calibration data, setup configuration, and any event data. Each log is saved as a .csv file for easy transfer.
The BL121 offers three 4-20 mA outputs for pH, ORP, and temperature. Each output may be disabled or connected to an external recording device and is adjustable to be proportional to the measured value. For greater flexibility and better resolution, the analog output can be scaled; users can define any two points within a parameter range to correspond to the analog output span. This adjustment allows better resolution in the range of interest.
For review and storage the users can easily transfer data to a PC using a flash drive and the USB port.
Hanna's BL121 controller features a password protection solution that offers restricted access to calibration, setup, and review of logged data. The password can be set and enabled/disabled during general setup of the instrument.


text:
The Books – Lost and Safe (Tomlab)
The Lemon of Pink was one of the oddest and most memorable releases of 2003: a follow-on to the previous year's odd-but-so-so Thoughts For Food, this was a completely un-self-conscious, fabulously hybrid creature – like a yodelling griffin, or a falsetto phoenix in a pink boa – consisting of two parts sound-collage, two parts nonsense, and one part quirky instrumentals. Few knew how to even begin to talk about it. It was just utterly delightful.
Lost and Safe is even better.
Sometime around 1900, some long-forgotten inmate of a lunatic asylum in either Germany, Switzerland, Italy, or France began tearing up scraps of paper and fabric and gluing them at random onto a canvas supplied by the establishment to keep its charges occupied. This 'object' was acquired, together with a hundred or so other examples of madmen's doodlings, by a psychiatrist called Hans Prinzhorn, resident at the Heidelberg Psychiatric Institute, who, beneath his other hat as an art historian, recognised that there might be something more to these formless, rootless, hallucinatory daubings than mere diagnostic auxiliaries. When the group of radical artists who were to become known as the Cubists were searching for an authenticity in art that would support their reaction to its current Academic domination, they first turned to 'primitive' art and childrens' drawings for inspiration, then they discovered the 'psychotic art' of the Prinzhorn Collection, and its effect was immediate and world-shaking. In 1912 in Paris, one Pablo Picasso pasted a patch of oilcloth with a chair-caning design to a canvas and called it 'Still Life with Chair Caning' ('Nature Morte à la chaise cannée') and the history of art was transformed: 'collage' was born.
Whereas a number of Modernist artists – notably the Dadaists and Surrealists – experimented with collage ideas in sound and live performance, it wasn't until the invention of magnetic tape as a recording device that the fundamental principles of cutting and pasting could properly be begun to be experimented with. Iannis Xenakis, working in the early 1960's, is recognised as being one of the first composers to work with sound-collage, then people like John Cage, Brion Gysin, and William S Burroughs picked up the torch and ran with it in their own distinctive directions.
In popular music, sound-collage made its first appearance, as so much else, with the Beatles: Being For the Benefit of Mr Kite on Sgt Pepper's Lonely Hearts Club Band, and Revolution No. 9 on The Beatles were the prototypes for a long and distinguished line of artists who have subsequently incorporated sampling into their work as a dominant, if not the defining aspect of their music: Girl Talk, Kid 606, People Like Us, DJ Shadow, Negativland, Set Fire to Flames … etc
A recent rash of petulant and silly lawsuits on the grounds of theft of intellectual copyright has rather queered the pitch for such artists lately (it'll all blow over by Christmas) but as The Books' sources seem mostly to be archival radio and TV tapes (a lot from the BBC), I can't see that being a problem. Not unless the estate of the late great Raymond Baxter, for starters, begins clamouring for royalties. RB was a Battle of Britain hero, one of The Few, a Spitfire pilot-turned-rally-driver-turned-radio commentator who subsequently established himself as one of the first TV popularists of science and new technology. In June 1962 he was present at the BBC's huge parabolic dish at Goonhilly Down on the Lizard edge of Cornwall to witness the very first live transatlantic transmission of a TV image bounced from Andover in Maine via the Telstar satellite. His 'Here we are…Here we are…We are antici…There it is! There it is!… It's a man! There it is!…' provides the opening sample to Be Good To Them Always, and, whereas you don't need to know that, it does inform the rest of the song in a very typically Bookian manner.
It's at the heart of the collage technique that, whereas the whole is composed of snippets from here there and everywhere, it's implied that those snippets carry their own resonance into the reassembly whether they're recognised or not. At the heart of the nonsense poem, that other significant component in The Books technical armoury, is the reverse notion: that, regardless of the apparent lack of sense in the superficial reading of the poem, or lyrics, meaning coheres nevertheless to the experience as an inevitable consequence of the human need to make sense of one's situation regardless of any and all disorientating distractions.
Originating (in the English tradition) with the tenth-century Anglo-Saxon Riddles and the Exeter Book, writers such as Lewis Carroll, Edward Lear, Ogden Nash, and Spike Milligan have become synonymous with the notion of 'nonsense', with, yet again, John Lennon himself deserving at least an honourable mention. Sergeant Pepper was Monty Python's uncle, of course. Not many people know that. The Books own contributions to the form are distinctive not so much for their content (prolix streams of consciousness operating just this side of tediousness) but for the astonishingly inventive ways in which they manage to shoe-horn the music to accompany them:
'most of all the world is a place where
parts of wholes are described
within an overarching paradigm of clarity'
is perfectly typical.
A plummy archive reading of part of Lewis Carroll's 'Jabberwocky' comprises the lyrical superstructure for most of Vogt Dig for Kloppervok which, unsurprisingly, translates as 'Beware the Jabberwock' in Danish. Here, something else typically Bookian: the re-constituting of a sound-collage assembly into a standalone sung 'chorus' – a kind of sonic equivalent of copying a visual collage as a separate picture. This is so post-post-Modern it's bleeding edge, but the marvellous thing about it is that it's not even remotely earnest in that dreadful, hermetic, knowing way that some artists adopt: it's just great fun. It's inclusive. It makes you smile. Rare gift.
The aforementioned quirky instrumentals – the third leg in The Books tripod – have evolved considerably since The Lemon of Pink. Now, not only do we have Nick Zammuto's guitar and Paul de Jong's cello – the fundamental basis of The Books sound pallette – but also much more of frequent collaborator Anne Doerner's perky banjo, and the inclusion of a whole battery of new, found, and altered instruments, including, notably, a vintage Hohner clavinet, a set of tuned plastic drainpipes, and a cheap metal filing cabinet with subwoofers installed inside: add these sounds to things like inside-out cello and slow-motion ringtones and you begin to get the picture. Quirky.
But never whimsical, unlike the only two other groups who I can think of to compare The Books with – Lemon Jelly and British Sea Power – who, for all that they're both marvellously distinctive and hugely enjoyable in their own, different ways, both succumb, occasionally, to what I think of as the Morris Dancing syndrome, when substance is subsumed to nostalgia, and the jingling and the hankies and the tambourines …. *shudder*
There's such an embarassment of riches in Lost and Safe.There's a piece of virtuoso filing-cabinet drumming on An Animated Description of Mr Maps that moves from a kind of Burundi masterclass to incorporating something I've only ever heard before in Steve Reich's Different Trains – when the percussion exactly matches the rhythm of the spoken word, which in this case is an animated description (just as it says on the label) of a strangely colourful-sounding police fugitive as read over some local radio network. And in It Never Changes To Stop Doerner's double-tracked banjo is joined by de Jong's double-tracked cello and finally by Zammuto's double-tracked guitar in an elegaic Rachels-like sextet that turns out to be the introduction to a very disturbing little outburst from a deeply stressed Southern state junior school teacher hectoring his cowed class into silence before prayers.
Lost and Safe is also the most song-based of The Books three albums so far: Nick actually sings – quite a lot – and really quite nicely – outstandingly in An Owl With Knees, an achingly beautiful, enigmatic song whose rolling instrumental break – just those three, unaltered, instruments, this time – emerges out of a fast-chopping pizzicato sequence that sounds for all the world as if Apocalypse Now's ubiquitous slowed-down helicopter sounds had been grafted onto a Bach chorale that ascends to quite inspirationally sublime heights before, literally, and most cruelly, just petering out at four-and-a-half minutes. More, they yelled, more.
There is, of course, another way of looking at all this. Having listened to this album a lot since acquiring it, I've begun to nurse the inkling of a suspicion that there might be something else at work here – that its paradoxical title might, in fact, be a clue, and that its eleven (!) tracks are code-cribs to the deciphering (come closer whilst I whisper this – and swear that you won't tell another soul) of the infamous Lost Books of the Illuminati.
'The books suggest we set our hearts on doing nothing' (A Little Longing Goes Away)
'When finally we opened the box.
we couldn't find any rules' (Smells Like Content)
'He saw red, but he thought five' (An Animated Description of Mr Maps)
'I can't find the books, they must be in La Jolla' (If Not Now, Whenever)
'It told itself it needed names
and in so doing it became' (Twelve Fold Chain)
Such apparent gobbledegook might well be nothing more nor less than a brilliant cryptic concealment, purposely disguising its portent beneath a double-bluff of nonsense.
It's happened before.
Me, I'm off to La Jolla. Or maybe Heidelberg.


Several graduates from Audencia Business School have set up companies in the field of CSR. The school's business incubator promotes the development of these projects and the CSR Institute supports the entrepreneurs, making available its expertise and network.
Here are a few companies created by Audencia graduates.