text:
\section*{Supplementary Material}
\lemapproxrecurrence*
\begin{proof}
First consider the $\epsilon_{k}$-greedy algorithm. We have
\begin{align*}
  f\left((1-\eta_{k}) w_{k} + \eta_{k} d_{k} \right)
    &\le \min_{d' \in S} f\left((1 - \eta_{k}) w_{k} + \eta_{k} d'\right) + \epsilon_{k} \\
    &\le \min_{d' \in S}
      \left(f(w_{k}) + \eta_{k} \grad f(w_{k})^\top (d' - w_{k}) + \frac{M}{2} \eta_{k}^2 \right)
      + \epsilon_{k} \\
    &\le f(w_{k}) + \eta_{k} \min_{d' \in S} \grad f(w_{k})^\top (d' - w_{k})
      + \epsilon'_{k} \\
    &\le f(w_{k}) + \eta_{k} (f(w^*) - f(w_{k})) + \epsilon'_{k}.
\end{align*}
Let $e_{k} = f(w_{k}) - f(w^*)$, and subtract both sides of the above inequality
by $f(w^*)$, we obtain
\begin{align*}
  e_{k+1} \le (1 - \eta_{k}) e_{k} + \epsilon'_{k}.
\end{align*}

For the $\epsilon_{k}$-greedy FW algorithm, we have
\begin{align*}
  f\left((1 - \eta_{k}) w_{k} + \eta_{k} d_{k}\right)
    &\le f(w_{k}) + \eta_{k} \grad f(w_{k})^\top (d_{k} - w_{k}) + \frac{M}{2} \eta_{k}^2 \\
    &\le f(w_{k}) + \eta_{k} (\min_{d' \in S} \grad f(w_{k})^\top (d_{k} - w_{k}) + \epsilon_{k})
      + \frac{M}{2} \eta_{k}^2 \\
    &\le f(w_{k}) + \eta_{k} \left(f(w^*) - f(w_{k})\right) + \eta_{k} \epsilon_{k}
      + \frac{M}{2} \eta_{k}^2.
\end{align*}
Subtracting both sides of the inequality by $f(w^*)$, we obtain
\begin{align*}
  e_{k+1} \le (1 - \eta_{k}) e_{k} + \epsilon'_{k}.
\end{align*}
\end{proof}

\thmrate*
\begin{proof}
Let $C = 2M+4c$.
From \Cref{lem:approx-recurrence}, for both $c$-greedy and $c$-FW algorithms, we have
\begin{align*}
	e_{k+1} \le (1 - \eta_{k}) e_{k} + \frac{C}{4} \eta_{k}^2.
\end{align*}
We prove the bound by induction.
Taking $k = 0$, we obtain $f(w_{1}) - f(w^*) \le \frac{C}{4} < \frac{C}{k+2}$.

For the inductive, assume the bound holds for $k$, that is,
$e_{k} \le \frac{C}{k+2}$, then we have
\begin{align*}
	e_{k+1}
    \le \left(1 - \frac{2}{k+2}\right) \frac{C}{k+2} + \frac{C}{(k+2)^2}
    = \frac{(k+1) C}{(k+2)^2}
    < \frac{C}{k+3},
\end{align*}
where the last inequality holds because
$(k+1) (k+3) = k^2 + 4k + 3 < (k+2)^2$.
\end{proof}

\thmequiv*
\begin{proof}
\noindent(a)
Suppose the current iterate is $w_k \in W$.
If a $\epsilon_{k}$-greedy algorithm yields $(\eta_k, d_k) \in [0, 1] \times S$, then
\begin{align*}
	&\quad f(w_{k}) + \eta_{k} \grad f(w_{k})^\top (d_{k} - w_{k})  \\
	&\le f\left((1-\eta_{k}) w_{k} + \eta d_{k} \right)
    && \text{(convexity)} \\
	&\le \min_{d' \in S} f\left((1 - \eta_{k}) w_{k} + \eta_{k} d'\right)
		+ \eta_{k} \epsilon_{k}
		&& (\text{$\epsilon_{k}$-greedy}) \\
	&\le \min_{d' \in S} \left(f(w_{k})
		+ \eta_{k} \grad f(w_{k})^\top (d'-w_{k})
		+ \frac{M}{2} \eta_{k}^2\right)
		+ \eta_{k} \epsilon_{k}
     && (\text{curvature assumption})\\
	&= f(w_{k})
		+ \eta_{k} \min_{d' \in S} \grad f(w_{k}) (d' - w_{k})
		+ \eta_{k} \left(\frac{M}{2} \eta_{k} + \epsilon_{k}\right)
\end{align*}
That is, we have
\begin{align*}
	f(w_{k}) + \eta_{k} \grad f(w_{k})^\top (d_{k} - w_{k})
    &\le f(w_{k})
			+ \eta_{k} \min_{d' \in S} \grad f(w_{k}) (d' - w_{k})
			+ \eta_{k} \left(\frac{M}{2} \eta_{k} + \epsilon_{k}\right).
\end{align*}
Simplifying the above inequality, we have (assuming $\eta_{k} \neq 0$ if $w_{k}$ is
not an optimal solution)
\begin{align*}
	\grad f(w_{k})^\top d_{k}
		\le \min_{d' \in S} \grad f(w_{k}) d'
			+ \frac{M}{2} \eta_{k} + \epsilon_{k}.
\end{align*}
The case for $c$-greedy algorithms follow easily.

\medskip\noindent(b)
Suppose the current iterate is $w_{k} \in W$.
If an algorithm is $\epsilon_{k}$-FW, then it gives a $(\eta_{k}, d_{k}) \in [0, 1] \times S$
such that for any $d' \in S$
\begin{align*}
	&\quad f\left((1-\eta_{k}) w_{k} + \eta_{k} d_{k}\right)  \\
  &\le f(w_{k})
		+ \eta_{k} \grad f(w_{k})^\top (d_{k} - w_{k})
		+ \frac{M}{2} \eta_{k}^2
    && \text{(curvature assumption)}\\
  &\le f(w_{k})
		+ \eta_{k} \grad f(w_{k})^\top (d'-w_{k})
		+ \eta_{k} \epsilon_{k}
		+ \frac{M}{2} \eta_{k}^2
    && \text{($c$-FW)} \\
  &\le f\left((1-\eta_{k}) w_{k} + \eta_{k} d'\right) +
		+ \eta_{k} (\epsilon_{k} + \frac{M}{2} \eta_{k})
    && \text{(convexity)}
\end{align*}
The case for $c$-greedy FW algorithms follow easily.
\end{proof}

\propasjeg*
\begin{proof}
Consider least squares regression
$\min_{w \in W} \sum_{i=1}^{3} (x_i^{\top} w - y_i)^2$, where
$x_1 = (0, 1)$,
$x_2 = (-\frac{\sqrt{3}}{2}, -\frac{1}{2})$,
$x_3 = (\frac{\sqrt{3}}{2}, -\frac{1}{2})$,
$y_1 = 1, y_2 = 1, y_3 = 1$, and
$S = \{x_1, x_2, x_3\}$.

It can be shown that $(\eta_k, d_k) = (1, x_i)$, that is,
$w_{k+1} = x_i$.
\end{proof}

\thmasj*
\begin{proof}
Let	$u_{k} = \argmin_{d \in S} f((1 - \eta_{k}) w_{k} + \eta_{k} d_{k})$.
We have
\begin{align*}
	&\quad \eta_{k} \grad \tilde{f}_{k}(w_{k})^{\top} (d_{k} - w_{k}) \\
		&= -\tilde{f}_{k}(w_{k})
			+ \tilde{f}_{k}(w_{k})
			+ \eta_{k} \grad \tilde{f}_{k}(w_{k})^{\top} (d_{k} - w_{k}) \\
		&\le -\tilde{f}_{k}(w_{k})
			+ \tilde{f}_{k}\left(w_{k} + \eta_{k}(d_{k} - w_{k})\right)
			&& (\text{convexity}) \\
		&\le -\tilde{f}_{k}(w_{k})
			+ \tilde{f}_{k}\left(w_{k} + \eta_{k}(u_{k} - w_{k})\right)
			+ c \eta_{k}^2
			&& (\text{approximate optimality of $d_{k}$}) \\
		&\le -\tilde{f}_{k}(w_{k})
			+ \tilde{f}_{k}(w_{k})
			+ \eta_{k} \grad \tilde{f}_{k}(w_{k})^{\top} (u_{k} - w_{k})
			+ \frac{M+2c}{2} \eta_{k}^2
			&& (\text{curvature assumption}) \\
		&= \eta_{k} \grad \tilde{f}_{k}(w_{k})^{\top} (u_{k} - w_{k})
			+ \frac{M+2c}{2} \eta_{k}^2. \numberthis \label{eq:asj1}
\end{align*}
We have
\begin{align*}
	&\quad f(w_{k+1}) \\
		&\le f(w_{k})
			+ \eta_{k} \grad f(w_{k})^{\top} (d_{k} - w_{k})
			+ \frac{M}{2} \eta_{k}^2 \\
		&= f(w_{k})
			+ \eta_{k} \grad \tilde{f}_{k}(w_{k})^{\top} (d_{k} - w_{k})
			+ \eta_{k} \left(\grad f(w_{k}) - \grad \tilde{f}_{k}(w_{k})\right)^{\top} (d_{k} - w_{k})
			+ \frac{M}{2} \eta_{k}^2 \\
		&\le f(w_{k})
			+ \left(\eta_{k} \grad \tilde{f}_{k}(w_{k})^{\top} (u_{k} - w_{k})
			+ \frac{M+2c}{2} \eta_{k}^2\right)
			+ \eta_{k} \left(\grad f(w_{k}) - \grad \tilde{f}_{k}(w_{k})\right)^{\top} (d_{k} - w_{k})
			+ \frac{M}{2} \eta_{k}^2 \\
		&= f(w_{k})
			+ \eta_{k} \grad f(w_{k})^{\top} (u_{k} - w_{k})
			+ \eta_{k} \left(\grad f(w_{k}) - \grad \tilde{f}_{k}(w_{k})\right)^{\top} (d_{k} - u_{k})
			+ (M + c) \eta_{k}^2 \\
		&\le f(w_{k})
			+ \eta_{k} (f(w^*) - f(w_{k}))
			+ \eta_{k} \left(\grad f(w_{k}) - \grad \tilde{f}_{k}(w_{k})\right)^{\top} (d_{k} - u_{k})
			+ (M + c) \eta_{k}^2 \\
		&\le f(w_{k})
			+ \eta_{k} (f(w^*) - f(w_{k}))
			+ \eta_{k} \norm{\grad f(w_{k}) - \grad \tilde{f}_{k}(w_{k})}_2 D
			+ (M + c) \eta_{k}^2,
\end{align*}
where the first inequality is due to the curvature assumption,
the second inequality due to \Cref{eq:asj1},
the third due to the duality bound,
and the last due to Cauchy-Schwarz and $\norm{d_{k} - u_{k}}_2 \le D$.
Now using convexity and telescoping the above inequality over $k$, we have
\begin{align*}
	&\quad (\sum_{k=1}^{t} \eta_{k}) \left(f(\bar{w}_{k}) - f(w^*)\right) \\
	&\le \sum_{k=1}^{t} \eta_{k} (f(w_{k}) - f(w^*)) \\
	&\le f(w_{1}) - f(w_{t+1})
			+ \sum_{k=1}^{t} \eta_{k} D \norm{\grad f(w_{k}) - \grad \tilde{f}_{k}(w_{k})}_2
			+ \sum_{k=1}^{t} (M + c) \eta_{k}^2.
\end{align*}
Using $f(w_{t+1}) \ge f(w^*)$,
taking expectation,
and using
${\mathbb E} \norm{\grad f(w_{k}) - \grad \tilde{f}_{k}(w_{k})}_2
\le \frac{L}{\sqrt{b}}$,\footnote{
This is because
$\left({\mathbb E} \norm{\grad f(w_{k}) - \grad \tilde{f}_{k}(w_{k})} \right)^2
\le {\mathbb E} \norm{\grad f(w_{k}) - \grad \tilde{f}_{k}(w_{k})}_2^2
= \frac{1}{b} {\mathbb E} \norm{\grad f_i(w_{k}) - \grad f(w_{k})}_2^2
\le \frac{1}{b} {\mathbb E} \norm{\grad f_i(w_{k})}_2^2
\le \frac{L^2}{b}$, where
$i$ is randomly drawn from $[n]$.}
we obtain
\begin{align*}
	&\quad {\mathbb E} f(\bar{w}_{t}) - f(w^*)
	\le \frac{f(w_1) - f(w^*)}{\sum_{k=1}^{t} \eta_{k}}
		+ \frac{\sum_{k=1}^{t} \eta_{k} b_k^{-1/2}}{\sum_{k=1}^{t} \eta_{k}} DL
		+ \frac{\sum_{k=1}^{t} \eta_{k}^2}{\sum_{k=1}^{t} \eta_{k}} (M+c).
\end{align*}

When $b_k = t$ and $\eta_k = t^{-1/2}$ for all $k$, we have
\begin{align}
	{\mathbb E} f(\bar{w}_{k}) - f(w^*)
	\le \frac{f(w_1) - f(w^*) + DL + M + c}{\sqrt{t}}.
\end{align}

When $b_k = k$, and $\eta_{k} = k^{-1/2}$, we have
\begin{align}
	{\mathbb E} f(\bar{w}_{k}) - f(w^*)
	\le \frac{f(w_1) - f(w^*) + (DL + M + c) (\ln t + 1)}{\sqrt{t}}.
\end{align}
\end{proof}

\propasfwega*
\begin{proof
Consider
$\min_{\norm{w}_2 \le r} \sum_{i=1}^2 (x_i^\top w - y_i)^2$, where
$x_1 = x_2 = x = (1,1)$, $y_1 = 1$, $y_2 = -1$, and $r = 1/2$.
Here we can take $S = \{w: \norm{w}_2 = r\}$.

We first show prove convergence.
Let $X_i$ be the random variable taking value 1 when $(x_1, y_1)$ is sampled
at iteration $i$, and value -1 otherwise.
Define $Y_{k+1} = (1 - \gamma_i) Y_{k} + \gamma_{k} X_{k}$, then
it can be verified that $w_{k} = Y_{k} x$.
In addition, we can show that $Y_{k}$ converges in probability to 0, which
implies that $Y_{k} x$ converges in probability to a minimizer $w^* =
(0,0)$ of $f(w)$, and thus ${\mathbb E}(f(w_{k})) - f(w^*)$ converges to 0.

We prove the concentration result of $Y_{k}$ for the more general case where
$X_i$'s are i.i.d. drawn from a distribution on $[a, b]$ with mean $\mu$,
instead of from the uniform distribution on \{-1, 1\}.
First we have $Y_{k} = \sum_{i=0}^{k} w_i X_i$, where
$w_i = \frac{2}{i+2} \frac{i+1}{i+3} \ldots \frac{k}{k+2} \le \frac{2}{k+2}$.
By Hoeffding's inequality, we have
\begin{align*}
  P(|Y_{k} - \mu| \ge \epsilon)
    &\le 2 e^{-2 \epsilon^2 / \sum_{i=0}^t (w_i b -  w_i a)^2}.
\end{align*}
Since each $w_i \le \frac{2}{k+2}$, we have
\begin{align*}
  P(|Y_{k} - \mu| \ge \epsilon)
    &\le 2 e^{-(k+2) \epsilon^2 / 2(b - a)^2}.
\end{align*}

We have
$\grad f_i(w_{k}) = 2 (x_i^\top w_{k} - y_i) x_i$,
and $\grad f(w_{k}) = 4 (x^\top w_{k}) x$.
In addition,
let $d_{k,i} = \argmin_{d \in S} \langle d, \grad f_i(w_{k})$, then
\begin{equation*}
  d_{k,i}
  = -r \sign(x_i^\top w_{k} - y_i) x_i / \norm{x_i}_2
  = r \sign(y_i) x_i / \norm{x_i}_2
  = \frac{\sign(y_i)}{2\sqrt{2}} x,
\end{equation*}
where the $\sign(x_i^\top w_{k} - y_i) = \sign(y_i)$ because
$x_i^\top w_{k}$ is not large enough to change the sign of $y_i$.
Hence we have
\begin{equation*}
  {\mathbb E}(d_{k}) = \frac{1}{2} d_{k,1} + \frac{1}{2} d_{k,2}  = 0.
\end{equation*}
On the other hand, we have
\begin{equation*}
  \argmin_{\norm{d}_2 \le r} \langle d, \grad f(w_{k}) \rangle
    = -r \sign(x^\top w_{k}) x / \norm{x}_2.
\end{equation*}
We thus obtain
\begin{align*}
  \langle {\mathbb E}(d_{k}), \grad f(w_{k}) \rangle
    - \min_{d \in S} \langle s, \grad f(w_{k})
  = 0 - \langle - r \sign(x^\top w_{k}) x / \norm{x}_2, 4 (x^\top w_{k}) x \rangle
  = 4r |x^\top w_{k}| \norm{x}_2.
\end{align*}
Note that $w_{k}$ has nonzero probability of being $x$, thus there is a
nonzero probability that the above difference equals
$4 r |x^\top w_{k}| \norm{x}_2 = 4\sqrt{2}$.
However $\eta_{k} = 2/(k+2)$ converges to 0, thus there is no constant $c$
such that
\begin{equation*}
  \langle {\mathbb E}(d_{k}), \grad f(w_{k}) \rangle
    - \min_{d \in S} \langle d, \grad f(w_{k}) \\
  \le c \eta_{k}
\end{equation*}
for all $k$ and all $w_{k}$.
\end{proof}

\propasfwegb*
\begin{proof}
Consider least squares regression
$\min_{||w||_2 \le r} \sum_{i=1}^{3} (x_i^T w - y_i)^2$, where
$r < 1$, $x_1 = (0, 1)$,
$x_2 = (-\frac{\sqrt{3}}{2}, -\frac{1}{2})$,
$x_3 = (\frac{\sqrt{3}}{2}, -\frac{1}{2})$, and
$y_1 = 1, y_2 = - 1, y_3 = -1$.

It can be shown that $w_k$ converges in probability to
$(0, 2r/3)$ as $k \to \infty$.
However, the optimal solution is $(0, r)$.
\end{proof}

\lemlazy*
\begin{proof
We have
\begin{align*}
	\frac{\rho}{2} \norm{w^*_{k} - w^*_{k+1}}_2^2
	&\le F_{k+1}(w^*_{k}) - F_{k+1}(w^*_{k+1})
		&& (\text{$F_{k+1}$ is $\rho$-strongly convex}) \\
	&= F_{s}(w^*_{k}) - F_{s}(w^*_{k+1}) + \sigma_{k} g_{k}^{\top} (w^*_{k} - w^*_{k+1})
		&& (\text{definition of $F_{k+1}$})\\
	&\le \sigma_{k} g_{k}^{\top} (w^*_{k} - w^*_{k+1})
		&& (\text{$F_{s}(w^*_{k}) \le F_{s}(w^*_{k+1})$}) \\
	&\le \sigma_{k} \norm{g_{k}}_2 \norm{w^*_{k} - w^*_{k+1}}_2.
	&& (\text{Cauchy-Schwarz})
\end{align*}
Hence we have $\norm{w^*_{k} - w^*_{k+1}}_2 \le \frac{2 \sigma_{k} \norm{g_{k}}_2}{\rho}$, and
this implies
\begin{align}
		\sigma_{k} g_{k}^{\top} (w*_{k} - w^*_{k+1}) \le \frac{2 \sigma_{k}^2 \norm{g_{k}}_2^2}{\rho}.
		\label{eq:lemlazy1}
\end{align}

We claim that
\begin{align}
  \sum_{i=1}^{s} \sigma_i g_i^{\top} (w^*_i - w)
    \le \sum_{i=1}^{s} \sigma_i g_i^{\top} (w^*_i - w^*_{i+1}) + \Phi(w) - \Phi(w^*_1).
		\label{eq:lemlazy2}
\end{align}
This is equivalent to
\begin{align*}
  \sum_{i=1}^{s} \sigma_i g_i^{\top} w^*_{i+1} + \Phi(w^*_1)
    \le \sum_{i=1}^{s} \sigma_i g_i^{\top} w + \Phi(w).
\end{align*}
This holds when $s = 0$ by the definition of $w^*_1$.
If this holds for some $s$, then this holds for $s+1$ as follows,
\begin{align*}
  \sum_{i=1}^{s+1} \sigma_i g_i^{\top} w^*_{i+1} + \Phi(w^*_1)
    \le \sum_{i=1}^{s} \sigma_i g_i^{\top} w^*_{s+2} + \sigma_{k+1} g_{k+1}^{\top} w^*_{s+2} + \Phi(w^*_{k+1})
    \le \sum_{i=1}^{s+1} \sigma_i g_i^{\top} w + \Phi(w).
\end{align*}
where the first inequality uses the inductive assumption, and the second one
holds by the definition of $w^*_{s+2}$.

Combining \Cref{eq:lemlazy1} and \Cref{eq:lemlazy2}, we have
\begin{align*}
	\sum_{k=1}^{t} \sigma_{k} g_{k}^{\top} (w^*_{k} - w)
	\le \sum_{k=1}^{t} \frac{2 \sigma_{k}^2 \norm{g_{k}}_2^2}{\rho} + \Phi(w) - \Phi(w^*_1).
	\le \sum_{k=1}^{t} \frac{2 \sigma_{k}^2 \norm{g_{k}}_2^2}{\rho} + R^2.
\end{align*}
\end{proof}

\lemsfwrecurrence*
\begin{proof
We first transform the recurrence in \Cref{eq:e} in the form
$e_{k+1} \le h(e_{k})$ for some function $h$.
For nonnegative numbers $A, B, C$ to satisfy $A \le B + C \sqrt{A}$, we need to have
$(\sqrt{A} - \frac{C}{2})^2 \le B + \frac{C^2}{4}$, or
$\sqrt{A} \le \sqrt{B + \frac{C^2}{4}} + \frac{C}{2}$.
This implies $A \le B + \frac{C^2}{2} + C \sqrt{B + \frac{C^2}{4}}$.
Applying this transformation to the recurrence in \Cref{eq:e}, we have
\begin{align}
  e_{k+1} &\le  (1 - \eta_{k}) e_{k} + \frac{\lambda R^2}{\rho} \eta_{k}^2
		+ \frac{\sigma_{k}^2 L^2}{\rho}
		+ \sqrt{\frac{2}{\rho}} \sigma_{k} L \sqrt{
				(1 - \eta_{k}) e_{k}
				+ \frac{\lambda R^2}{\rho} \eta_{k}^2
				+ \frac{\sigma_{k}^2 L^2}{2\rho}} \nonumber \\
		&\le A' + \sqrt{\frac{2}{\rho}} \sigma_{k} L \sqrt{A'}
		\label{eq:e_{k}+1}.
\end{align}
where
$A' = (1 - \eta_{k}) e_{k}
+ \frac{\lambda R^2}{\rho} \eta_{k}^2
+ \frac{c^2 L^2}{\rho} \eta_{k}^2$.
The second inequality holds by observing that $\frac{\sigma_{k}^2 L^2}{\rho}$
and $\frac{\sigma_{k}^2 L^2}{2\rho}$ in the first inequality are smaller than
$\frac{c^2 L^2}{\rho}\eta_{k}^2$, because
$\sigma_{k}^2 = c^2 \eta_{k}^3 \le c^2 \eta_{k}^2$.

Now we find a value of $K$ by determining a sufficient condition on $K$ such
that $e_{k+1} \le K \eta_{k+1}$ holds when $e_{k} \le K \eta_{k}$.
Assume $e_{k} \le K \eta_{k}$ for some $s$, then
\begin{alignat}{3}
	e_{k+1} &\le K \eta_{k+1}
	&\quad\Longleftarrow\quad&&
		A' + \sqrt{\frac{2}{\rho}} \sigma_{k} L \sqrt{A'} &\le K \eta_{k+1}
		\label{eq:back1} \\
	&&\quad\Longleftarrow\quad&&
		A' + \sqrt{\frac{2}{\rho}} c L \sqrt{K} \eta_{k}^{2} &\le K \eta_{k+1}
		\label{eq:back2} \\
	&&\quad\Longleftrightarrow\quad&&
		(1 - \eta_{k}) K \eta_{k} + M \eta_{k}^2 &\le K \eta_{k+1}
		\label{eq:back3} \\
	&&\quad\Longleftrightarrow\quad&&
	\frac{K}{K - M} &\le \frac{\eta_{k}^2}{\eta_{k} - \eta_{k+1}}
		\label{eq:back4} \\
	&&\quad\Longleftarrow\quad&&
	\frac{K}{K - M} &= \frac{1}{p},
		\label{eq:back5}
\end{alignat}
where $M = \frac{\lambda R^2 + c^2 L^2}{\rho} + \sqrt{\frac{2}{\rho}} cL \sqrt{K}$.
\begin{itemize}
\item
When \Cref{eq:back1} holds, then from \Cref{eq:e_{k}+1}, we have
$e_{k+1} \le K \eta_{k+1}$.
\item
When \Cref{eq:back2} holds, we have $K \eta_{k} > K \eta_{k+1} > A'$.
Thus
$A' + \sqrt{\frac{2}{\rho}} c L \sqrt{K} \eta_{k}^{2}
= A' + \sqrt{\frac{2}{\rho}} c \eta_{k}^{3/2} L \sqrt{K \eta_{k}}
\ge A' + \sqrt{\frac{2}{\rho}} \sigma_{k} L \sqrt{A'}$.
\item
Both \Cref{eq:back3} and \Cref{eq:back4} are just rewriting of the previous
inequality.
\item
To show that \Cref{eq:back5} implies \Cref{eq:back4}, it suffices to show
that $\frac{\eta_{k}^2}{\eta_{k} - \eta_{k+1}} \ge \frac{1}{p}$ for any
$s \ge 1$.
Using calculus, we have
$(1 + \frac{1}{k})^p
\le 1 + \frac{p}{k}
\le 1 + \frac{p}{k^p}$ for $k \ge 1$.
Hence we have
$\eta_{k} - \eta_{k+1}
= \frac{1}{k^p} - \frac{1}{(k + 1)^p}
= \frac{1}{(k + 1)^p} \left(\frac{(k+1)^p}{k^p} - 1\right)
= \frac{1}{(k+1)^p} \left((1 + \frac{1}{k})^p - 1\right)
\le \frac{1}{(k+1)^p} \frac{p}{k^p}$.
It follows that
$\frac{\eta_{k}^2}{\eta_{k} - \eta_{k+1}} \ge \frac{1}{p} \frac{(k+1)^p}{k^{p}} \ge \frac{1}{p}$.
\end{itemize}
Now we solve \Cref{eq:back5}.
This is equivalent to
$K = \frac{M}{1-p}
= \frac{\lambda R^2 + c^2 L^2}{\rho(1-p)}
	+ \sqrt{\frac{2}{\rho}}\frac{cL}{1-p} \sqrt{K}$,
which is equivalent to
$(\sqrt{K} - \sqrt{\frac{1}{2\rho}} \frac{cL}{1-p})^2
	= \frac{\lambda R^2 + c^2 L^2}{\rho(1-p)}
		+ \frac{c^2 L^2}{2 \rho (1-p)^2}$,
or
\begin{align*}
K =
	\left(\sqrt{\frac{1}{2\rho}} \frac{cL}{1-p}
		+ \sqrt{\frac{\lambda R^2 + c^2 L^2}{\rho(1-p)}
		+ \frac{c^2 L^2}{2 \rho (1-p)^2}}\right)^2.
\end{align*}

To complete the proof it suffices to show that $e_{1} \le K \eta_1$.
This holds because
\begin{align*}
	e_1 = F_1(w_1) - F_1(w^*_1) = \Phi(w_1) - \Phi(w^*_1) = 0 < K \eta_1.
\end{align*}
\end{proof}

\section{Introduction}

Consider the following problem of minimizing a convex function over a convex set,
\begin{align}
  \min_{w \in W} f(w),
\end{align}
where $W$ is the convex hull of a set of atoms $S$ in a linear
vector space.
Such problem occurs frequently in machine learning and engineering
\citep{boyd2004convex}.
We consider greedy algorithms which starts with some
$w_1 \in W$, and then iteratively find
$w_{k+1} = (1 - \eta_{k}) w_{k} + \eta_{k} d_{k}$, where
$\eta_{k}$ and/or $d_{k} \in S$ are greedily chosen according to certain
criterion.
An attractive feature of such algorithm is that the iterates are sparse,
because each iteration adds at most one new atom in $S$.

Two greedy algorithms are well-known:
an algorithm originally studied by \citet{jones1992simple},
and the Frank-Wolfe (FW) algorithm \citep{frank1956algorithm}.
Jones' algorithm chooses
\begin{align*}
	(\eta_{k}, d_{k})
	= \argmin_{\eta \in [0,1], d \in S} f(\eta w_{k} + (1 - \eta) d).
\end{align*}
This has been studied in various contexts,
such as function approximation in the Hilbert space
\citep{jones1992simple,barron1993universal,lee1996efficient},
$\ell_p$ regression \citep{donahue1997rates},
density estimation \citep{li1999mixture}, and is closely related to
boosting \citep{zhang2003sequential}.
The FW algorithm chooses
\begin{align*}
	d_{k} = \argmin_{d \in S} \grad f(w_{k})^{\top} d,
\end{align*}
and chooses $\eta_k$ by line search or a priori.
The FW algorithm has recently attracted significant interest due to
its projection-free property and the ability to handle structural constraints
\citep{jaggi2013revisiting}.
In contrast to solving quadratic programs for projection in projected gradient
descent and for the proximal map in the proximal algorithms, the FW
algorithm solves a linear program at each step, which is often computationally
more tractable \citep{jaggi2010simple,lacoste2013affine}.
Approximate versions of Jones' algorithm and the FW algorithm have also been
studied, for example, see \citep{zhang2003sequential,jaggi2013revisiting}.

In this paper, we first consider approximate versions of Jones' algorithm and
the FW algorithm, with a more general approximate version for Jones'
algorithm.
We focus on smooth convex functions in our analysis, and give a sufficient
convergence condition for both algorithms\showthmname{thm:converge}.
Building on previous results on the $O(1/k)$ convergence rates for both
algorithms, we present a unified analysis for the $O(1/k)$ convergence
rate\showthmname{thm:rate}, and also show that this is the optimal that can be
obtained with the proof technique\showthmname{thm:optimal}.
We also show that the approximate Jones' algorithm and the approximate FW
algorithm are equivalent\showthmname{thm:equiv}.

We then consider stochastic versions of these approximate greedy algorithms
for the stochastic approximation problem, where $f$ is an expectation ${\mathbb E}
f_{z}(w)$ over some random variable $z$.
We show that some stochastic versions fail even on smooth convex functions.
We give an approximate stochastic Jones algorithm that has error $\epsilon$
using $O(\epsilon^{-4})$ random $f_{z}(w)$ for smooth convex functions.
We also give an approximate stochastic FW algorithm that has an error
$\epsilon$ using $O(\epsilon^{-4})$ stochastic gradients and
$O(\epsilon^{-2})$ linear optimizations.
In addition, we give an approximate stochastic Frank-Wolfe algorithm that has
error $\epsilon$ using $O(\epsilon^{-4})$ stochastic gradients for nonsmooth
convex functions.
The algorithms also apply to the finite-sum setting where
$f(w) = \frac{1}{n} \sum_{i=1}^n f_i(w)$.
The finite-sum form occurs when performing empirical risk minimization in
machine learning, or when performing M-estimation in statistics.
In both cases, each $f_i$ measures how well a model fits an example.

Stochastic algorithms originated in the 1950s \citep{robbins1951stochastic},
and have attracted much interest in recent years, mainly due to its ability
to scale up to large datasets.
We note that stochastic FW algorithms have recently been considered for
smooth functions by \citet{reddi2016stochastic-b} and
\citet{hazan2016variance}.
\citet{reddi2016stochastic-b} considered the non-convex setting, and shows
that one can achieve an error of $\epsilon$ with $O(\epsilon^{-4})$ stochastic
gradients and $O(\epsilon^{-2})$ linear optimizations.
When $f$ is a finite sum, the number of stochastic gradients needed can be
reduced to $O(n + n^{1/3} \epsilon^{-2})$.
\citet{hazan2016variance} considered the convex setting, and showed that one
can achieve an error of $\epsilon$ with $O(\ln \epsilon^{-1})$ full gradients,
$O(\epsilon^{-2})$ stochastic gradients, and $O(\epsilon^{-1})$ linear
optimizations.
The number of stochastic gradients can be reduced to $O(\ln \epsilon^{-1})$
if $f$ is strongly-convex.
Both works use recent variance reduction techniques in convex optimization,
such as the works of
\citet{johnson2013accelerating,mahdavi2013mixed,defazio2014saga}.
\citet{hazan2016variance} additionally uses
\citet{nesterov1983method}'s acceleration technique.
They use exact greedy steps, instead of approximate greedy steps as in this
paper.

For the non-stochastic case, faster rates for FW are known with additional
assumptions \citep{lacoste2015global,garber2015faster,garber2016linearly}.
We refer the readers to the works of \citet{hazan2016variance} and
\citet{reddi2016stochastic-b} for further related works.

\section{Approximate Greedy Optimization}
We consider the approximate Jones' algorithm in \Cref{alg:greedy}.
At each iteration, the algorithm solves the optimization problem
$\min_{d \in S} f\left((1 - \eta_{k}) w_{k} + \eta_{k} d\right)$
with an error of $\epsilon_{k} \eta_{k}$.
We call this an $\epsilon_{k}$-approximate Jones' algorithm, and we say the algorithm is a
$c$-Jones algorithm if there is a constant $c \ge 0$ such that
$\epsilon_{k} \le c \eta_{k}$ for all $k$.

\begin{algorithm}[h!]
\caption{Approximate Jones' Algorithm}
\label{alg:greedy}
\begin{algorithmic}
\State Choose $w_0 \in W$.
\For{$k = 0, 1, 2, \ldots$}
	\State Choose $(\eta_{k}, d_{k}) \in [0, 1] \times S$ at iteration $k$ such that
		\begin{align}
			f\left((1 - \eta_{k}) w_{k} + \eta_{k} d_{k} \right) \le \min_{d \in S}
				f\left((1 - \eta_{k}) w_{k} + \eta_{k} d\right) + \epsilon_{k} \eta_k.
		\end{align}
	\State $w_{k+1} = (1 - \eta_{k}) w_{k} + \eta_{k} d_{k}$.
\EndFor
\end{algorithmic}
\end{algorithm}

We leave the choice of $\eta_{k}$ unspecified,
and thus this includes algorithms which fix $\eta_{k}$ a priori,
or choose $\eta_{k}$ and $d_{k}$ jointly at each iteration.
Similarly, $\epsilon_{k}$ may be chosen a priori or chosen adaptively.

An algorithm is called an $\epsilon_{k}$-approximate FW
algorithm, if given $w_{k} \in W$, the algorithm yields
$(\eta_{k}, d_{k}) \in [0, 1] \times S$ such that
\begin{align}
  \grad f(w_{k})^\top d_{k} \le \min_{d \in S} \grad f(w_{k})^\top d + \epsilon_{k},
\end{align}
and we say the algorithm is a $c$-FW algorithm for some $c \ge 0$ if
$\epsilon_{k} \le c \eta_{k}$.

\subsection{Assumptions}
In this section, we assume $f$ is convex with bounded curvature, that is,
\begin{align}
	f(w') \ge f(w) + \grad f(w)^{\top} (w' - w),
		\quad\text{for all $w', w \in W$,}
		&&& \text{(convexity)}\\
	\sup_{w \in W, d \in S, \eta \in (0,1)}
    \frac{2}{\eta^2} D_f\left((1-\eta) w  + \eta d, w\right)
		< \infty,
		&&& \text{(bounded curvature)}
\end{align}
where $D_f(w, y) = f(w) - f(y) - \grad f(y) (w - y)$ is the Bregman
divergence of $f$, and the LHS of the second equation is called the
\emph{curvature} of $f$ in $W$.
This definition of curvature is the same as that in
\citep{jaggi2013revisiting}, except that \citet{jaggi2013revisiting} takes
supremum over $d \in W$.
If $f$ is $L$-smooth, that is,
$\norm{\grad f(w') - \grad f(w)}_2 \le L \norm{w' - w}_2$ for all
$w', w \in W$,
then the curvature of $f$ is not more than $L \diam(S)^2$.
Thus a smooth function has bounded curvature.
The curvature of $f$ is also not more than
  $\sup_{w \in W, d \in S, \eta \in (0,1)}
		\frac{\partial f((1-\eta) w + \eta d)}{\partial \eta^2}$,
assuming the second-order derivative exists.

The following are two basic bounds needed in our analysis.
\begin{lem}
(a) (Duality bound) If $f$ is convex on $W$,
$w^* = \argmin_{w \in W} f(w)$, then
for any $w \in W$,
\begin{align}
  f(w) - f(w^*)

		\le \max_{d \in S} f(w)^\top (w - d). \label{eq:duality}
\end{align}
(b) (Curvature inequality) If $f$ has curvature at most $M$, then for any $w \in W$,
$d \in S$, $\eta \in [0, 1]$,
\begin{align}
  f\left((1 - \eta) w + \eta d\right)
    &\le f(w) + \eta \grad f(w)^\top (d - w) + \frac{M}{2} \eta^2.
		\label{eq:curvature}
\end{align}
\end{lem}
\begin{proof}
(a) Using the definitions, we have
	\begin{align*}
		f(w) - f(w^*)
     \le \grad f(w)^\top (w - w^*)
     \le \max_{d \in W} f(w)^\top (w - d)
    \le \max_{d \in S} f(w)^\top (w - d).
	\end{align*}

(b) From the definition of Bregman divergence, we have
\begin{align*}
  f\left((1 - \eta) w + \eta d\right)
  = f(w) + \eta \grad f(w)^\top (d - w)
  + D_f\left((1 - \eta) w + \eta d \right).
\end{align*}
Apply the definition of curvature, then the desired inequality follows.
\end{proof}

In general, we cannot improve the quadratic term to a higher-order one in the
curvature inequality.
For example, if $f$ is $m$-strongly convex, then we can show that
$\sup_{w \in W, d \in S, \eta \in (0,1)}
\frac{1}{\eta^3} D_f\left((1-\eta) w  + \eta d, w\right)$ is infinity.

\subsection{A Sufficient Condition for Convergence}

The core to our convergence analysis for Jones' algorithm and the FW
algorithm is the following recurrence equation for the
error $e_{k} = f(w_{k}) - f(w^*)$.

\begin{restatable}{lem}{lemapproxrecurrence} \label{lem:approx-recurrence}
Let $f$ be convex with curvature at most $M$.
Then for both $\epsilon_{k}$-approximate Jones' algorithm and
$\epsilon_{k}$-approximate FW algorithm the error
$e_{k} = f(w_{k}) - f(w^*)$ satisfies
\begin{align}
	e_{k+1} \le (1 - \eta_k) e_{k} + \epsilon'_{k},
\end{align}
where $\epsilon'_{k} = \eta_k \epsilon_k + \frac{M}{2} \eta_k^2$.
\end{restatable}
We omit the proof of this lemma and a few other proofs in the main text, but
put them in the supplementary material, due to space limit.

The above lemma leads to a general convergence result for Jones' algorithm and
the FW algorithm.
\begin{restatable}{thm}{converge} \label{thm:converge}
Let $f$ be convex with curvature at most $M$.
For an $\epsilon_{k}$-approximate Jones' algorithm or an
$\epsilon_{k}$-approximate FW algorithm, if
$\eta_{k}$'s and $\epsilon_{k}$'s are chosen such that $\sum_{k} \eta_{k}$
diverges, $\eta_{k} \to 0$ and $\epsilon_{k} \to 0$ as $k \to \infty$, then
$f(w_{k}) \to f(w^*)$ as $k \to \infty$.
\end{restatable}
\begin{proof}
From \Cref{lem:approx-recurrence}, it suffices to show that under the given
conditions on $\eta_{k}$ and $\epsilon_{k}$, the solution to the recurrence
equation $e_{k+1} \le (1 - \eta_{k}) e_{k} + \epsilon'_{k}$ satisfies
$e_{k} \to 0$.

For any $\delta$ such that $0 < \delta < 1$, there exists $K$ such that
for all $k > K$, we have
	$\eta_{k} < \delta$,
	$\epsilon'_{k} / \eta_{k} < \delta / 2$,
because $\eta_{k} \to 0$ and $\epsilon_{k} / \eta_{k} \to 0$.
For any $k > K$, if $e_{k} > \delta$, then we have
\begin{align*}
  e_{k+1} \le e_{k} + \eta_{k} (\epsilon'_{k} / \eta_{k} - e_{k})
    \le e_{k} - \eta_{k} \delta / 2.
\end{align*}
Since $\sum_{k} \eta_{k}$ diverges, thus if $e_{k} > \delta$, then there exists
$N > K$ such that $e_{N} \le \delta$.
We show by induction that all $k \ge N$, we have $e_{k} \le \delta$.
This is true for $k = N$.
For the inductive case, assume $e_{k} \le \delta$.
If $e_{k} \ge \delta / 2$, then $\epsilon'_{k}/\eta_{k} - e_{k} \le 0$, and
thus
$e_{k+1} \le e_{k} + \eta_{k} ( \epsilon'_{k}/\eta_{k} - e_{k}) \le \delta$.
If $e_{k} \le \delta / 2$, then
$e_{k+1} \le \frac{\delta}{2} + \delta ( \frac{\delta}{2} - 0) \le \delta$.
We have thus proved that for any $\delta > 0$, there exists $N$ such that for
all $k \ge N$, $e_{k} \le \delta$.
Thus $e_{k} \to 0$ as $k \to \infty$.
\end{proof}

\subsection{Convergence Rate}
We now show that with proper choices of $\eta_{k}$'s and $\epsilon_{k}$'s, we can
obtain a convergence rate of $O(1/k)$ for Jones' algorithm and the FW algorithm.
\begin{restatable}{thm}{thmrate} \label{thm:rate}
Let $f$ be convex with curvature at most $M$,
$\eta_{k} = \frac{2}{k+2}$ for $k \ge 0$.
Then for the iterates $(w_{k})$ obtained
using a $c$-Jones algorithm or a $c$-FW algorithm, when $k \ge 1$,
\begin{align}
  f(w_{k}) - f(w^*) \le \frac{2M+4c}{k+2}.
\end{align}
\end{restatable}

The constant in the rate can be improved in some cases.
For example, if the minimizer is an algebraic interior point, then we can
get a smaller constant using an argument similar to that in
\citep{zhang2003sequential}.

A careful look at the analysis shows that if our update rule is guaranteed to
generate a new iterate that is not more than that generated by a $c$-FW
algorithm or a $c$-Jones algorithm with step size $\eta_k = 2/(k+2)$, then we
can get an $O(1/k)$ convergence rate.
This also implies that we can mix $c$-FW steps and $c$-Jones steps to get an
$O(1/k)$ convergence rate.
In addition, we can obtain the following result from \citet{zhang2003sequential} as
a special case.

\begin{cor}
Let $f$ be convex with curvature at most $M$.
If $w_{k+1} \in W$ is chosen such that
\begin{align*}
	f(w_{k+1})
	\le \min_{\eta \in [0,1], d \in S}
	f\left((1 - \eta) w_{k} + \eta d\right) + \frac{4c}{(k+2)^2},
\end{align*}
where $c > 0$ is some constant, then for $k \ge 1$, we have
$f(w_{k}) - f(w^*) \le \frac{2M + 4c}{k+2}$.
\end{cor}

The key idea in the above analysis is to show that
$e_{k+1} \le (1 - \eta_{k}) e_{k} + C \eta_{k}^2$,
and then use induction to show that $e_{k} \in O(\frac{1}{k})$ when
$\eta_{k} = \frac{2}{k+2}$.
Can we tune $\eta_{k}$ to obtain a bound $O(\frac{1}{k^p})$ for some $p > 1$?
It turns out that $p = 1$ is the best obtainable.
\begin{thm} \label{thm:optimal}
Consider a sequence $(e_{k})$ satisfying
\begin{align}
  e_{k+1} = (1 - \eta_{k}) e_{k} + C \eta_{k}^2,
\end{align}
with $e_0 \le 2C$, then for any choice of $\eta_{k}$, we have
$e_{k} \ge \frac{a}{k+2}$ for $a = \min\{e_0, C\}$.
\end{thm}
\begin{proof}
Clearly $e_0 \ge \frac{a}{2}$ holds.
Now we show by induction that if $e_{k} \ge \frac{a}{k+2}$, then
$e_{k+1} \ge \frac{a}{k+3}$.
Note that $(1 - \eta_{k}) e_{k} + C \eta_{k}^2$ is minimized when
$\eta_{k} = \frac{e_{k}}{4C}$, with minimum value $e_{k} (1 - \frac{e_{k}}{4C})$,
which is an increasing function of $e_{k}$ when
$e_{k} \in [\frac{a}{k+2}, 2C]$.
This implies that when $\eta_{k}$'s are chosen to minimize $e_{k}$'s, then $e_{k}$'s
form a decreasing sequence.
Since $e_0 \le 2C$, this also implies the minimum $e_{k} \le 2C$.
Hence we have
\begin{align*}
  e_{k+1}
    \ge e_{k} \left(1 - \frac{e_{k}}{4C}\right)
    \ge \frac{a}{k+2} \left(1 - \frac{a/4C}{k+2}\right)
    \ge \frac{a(k+2 - a/4C)}{(k+2)^2}
    \ge \frac{a}{k+3},
\end{align*}
where the last inequaliy holds because
\begin{align*}
  (k+2 - a/4C)(k+3)
  \ge (k + 2 - 1/4)(k+3)
  \ge k^2 + \frac{19}{4} k + \frac{21}{4}
  \ge (k+2)^2.
\end{align*}
\end{proof}

\subsection{An Equivalence Result}
We have already seen that a few results hold for both the approximate Jones'
algorithm and the approximate FW algorithm.
The following theorem shows that we can view these two algorithms as
equivalent algorithms.

\begin{restatable}{thm}{thmequiv} \label{thm:equiv}
Assume $f$ is convex with curvature at most $M$.
\begin{itemize}[leftmargin=1.5em]
\item[(a)] An $\epsilon_{k}$-approximate Jones' algorithm with step sizes $(\eta_{k})$ is
$(\epsilon_{k} + \frac{M}{2} \eta_{k})$-FW.
In particular, a $c$-Jones algorithm is $\frac{M+2c}{2}$-FW with the same step sizes.
\item[(b)] An $\epsilon_{k}$-approximate FW algorithm with step sizes $(\eta_{k})$ is
an $(\epsilon_{k} + \frac{M}{2} \eta_{k})$-approximate Jones' algorithm.
In particular, a $c$-FW algorithm is $\frac{M+2c}{2}$-Jones with the same step
sizes.
\end{itemize}
\end{restatable}

An immediate consequence of this result is that if any $c$-Jones algorithm
converges at $O(1/k)$ rate, then any $c$-FW algorithm converges at $O(1/k)$
rate too.

\section{Approximate Stochastic Greedy Optimization}

We consider approximate stochastic versions of Jones' algorithm and the FW
algorithm for optimizing a function $f(w) = {\mathbb E} f_z(w)$, where the
expectation is over a random variable.
Without loss of generality, we work with the finite-sum case where
$f(w) = \frac{1}{n} \sum_{i=1}^{n} f_i(w)$ to ease presentation.

\vspace{-0.5em}
\subsection{Stochastic Jones' Algorithm}
A natural stochastic version of Jones' algorithm is
obtained by replacing the function $f$ with a sampled approximation
$\tilde{f}_{k}$ at iteration $k$.

\begin{algorithm}[h!]
	\caption{Approximate Stochastic Jones (ASJ)}
	\label{alg:sg}
	\begin{algorithmic}
	\State Choose $w_1 \in W$.
	\For{$k = 1, 2, \ldots$}
		\State Sample a set $I_{k}$ of $b_k$ numbers independently and uniformly from $[n]$, and let
			\begin{align}
				\tilde{f}_{k}(w) = \frac{1}{b_k} \sum_{i \in I_{k}} f_i(w).
			\end{align}
		\State Choose $(\eta_{k}, d_{k}) \in [0,1] \times S$ such that
			\begin{align}
				\tilde{f}_{k}\left((1 - \eta_{k}) w_{k} + \eta_{k} d_{k} \right) \le \min_{d \in S}
					\tilde{f}_{k}\left((1 - \eta_{k}) w_{k} + \eta_{k} d\right) + \eta_{k} \epsilon_{k}.
			\end{align}
		\State $w_{k+1} = (1 - \eta_{k}) w_{k} + \eta_{k} d_{k}$.
	\EndFor
	\end{algorithmic}
\end{algorithm}

We show that ASJ is over-greedy when $b_k=1$ and the minimization
problem at each iteration is solved exactly.
The iterates can jump randomly from one vertex to another, leading to divergence.
This differs from the nonstochastic case where exact minimization leads to
smaller errors.
\begin{restatable}{prop}{propasjeg} \label{prop:asj-eg}
Let $b_{k} = 1$, $\epsilon_{k} = 0$ and $\eta_{k}$ jointly optimized with
$d_{k}$ in ASJ, then there exists a function
$f(w) = \frac{1}{n} \sum_{i=1}^{n} f_i(w)$ with each $f_i$ being convex
and smooth, such that ${\mathbb E} f(w_k) - f(w^*)$ does not converge to 0 as
$k \to \infty$.
\end{restatable}
On the other hand, we can get a convergent algorithm using increasingly
larger batch size.
In essence, the theorem below shows that when we choose a batch size of $k$ a
iteration $k$ with a step size $\sqrt{k}$, we can get an error of
$O(1/\sqrt{t})$ at any iteration $t$.
Taking $b_{k}$ as a measure of the computational complexity of the $k$-th
problem, then to get an error of $\epsilon$, the complexity of the algorithm
is $O(\epsilon^{-4})$.

\begin{restatable}{thm}{thmasj} \label{thm:asj}
Assume that the diameter of $W$ is $D$, each
$f_i(w)$ is convex with curvature at most $M$, and
$\norm{\grad f_i(w)}_2 \le L$ for all $i$ and $w \in W$.
Let $\bar{w}_{k} = \sum_{i=1}^{k} \eta_{i} w_{i} / \sum_{i=1}^{k} \eta_{i}$.
In ASJ, when $b_{k} = t$, $\eta_{k} = t^{-1/2}$ and
$\epsilon_{k} = c \eta_{k}$ for all $k$, we have
\begin{align}
	{\mathbb E} f(\bar{w}_{t}) - f(w^*)
	\le \frac{f(w_1) - f(w^*) + DL + M + c}{\sqrt{t}},
\end{align}
When $b_k = k$, and $\eta_{k} = k^{-1/2}$, we have
\begin{align}
	{\mathbb E} f(\bar{w}_{k}) - f(w^*)
	\le \frac{f(w_1) - f(w^*) + (DL + M + c) (\ln t + 1)}{\sqrt{t}}.
\end{align}
\end{restatable}

\subsection{Approximate Stochastic Versions of Frank-Wolfe}

For FW, we can also sample a mini-batch estimation of the function $f(w)$
and use the gradient of the estimation to replace the gradient of $f$, as
shown in \Cref{alg:asfw}.

\begin{algorithm}
	\caption{Approximate Stochastic Frank Wolfe (ASFW)}
	\label{alg:asfw}
	\begin{algorithmic}
	\State Choose $w_0 \in W$.
	\For{$k = 0, 1, 2, \ldots$}
		\State Sample a set $I_{k}$ of $b_k$ numbers independently and uniformly from $[n]$, and let
			\begin{align}
				\tilde{f}_{k}(w) = \frac{1}{b_k} \sum_{i \in I_{k}} f_i(w).
			\end{align}
		\State Choose $d_{k} \in S$ such that
			\begin{align}
				\grad \tilde{f}_{k}(w_{k})^{\top} d_{k}
					\le \min_{d \in S} \grad \tilde{f}_{k}(w)^{\top} d + \epsilon_{k}.
			\end{align}
		\State $w_{k+1} = (1 - \eta_{k}) w_{k} + \eta_{k} d_{k}$.
	\EndFor
	\end{algorithmic}
\end{algorithm}

We can show that if there exists a constant $c > 0$, for all $k \ge 0$, we have
\begin{align}
  \langle {\mathbb E}(d_{k}), \grad f(w_{k}) \rangle
    \le \min_{d \in S} \langle d, \grad f(w_{k}) \rangle + c \eta_{k},
	\label{eq:expect}
\end{align}
then ${\mathbb E}(f(w_k)) - f(w^*)$ is of the order $O(1/k)$ for $k \ge 1$.
The above recursive property is a sufficient but not necessary condition for
ASFW to have $O(1/k)$ convergence rate.
Indeed, there are cases where the above recursive property does not hold, but
ASFW converges.

\begin{restatable}{prop}{propasfwega} \label{prop:asfw-eg-a}
Let $b_{k} = 1$, $\epsilon_{k} = 0$, $\eta_{k} = \frac{2}{k+2}$ in ASFW.
There exists a function $f(w) = \frac{1}{n} \sum_{i=1}^{n} f_i(w)$ with
each $f_i$ being convex and smooth, such that
${\mathbb E} f(w_{k}) \to f(w^*)$ as $k \to \infty$ but
\Cref{eq:expect} is not satisfied.
\end{restatable}

\begin{restatable}{prop}{propasfwegb} \label{prop:asfw-eg-b}
Let $b_{k} = 1$, $\epsilon_{k} = 0$, and $\eta_{k}$ be arbitrarily chosen in
ASFW.
There exists a convex and smooth $f$ such that
$\lim_{k \to \infty} {\mathbb E} f(w_{k})$ exists, but the limit is
larger than $f(w^*)$.
\end{restatable}

\citet{reddi2016stochastic-b} considered the exact version of ASFW, that is,
the case with $\epsilon_{k} = 0$.
They showed that for smooth nonconvex $f$, with suitale
choice of $b_{k}$ and $\eta_{k}$, one can achieve an error of $\epsilon$ with
$O(\epsilon^{-4})$ stochastic gradients and $O(\epsilon^{-2})$ linear
optimizations.
We remark here that we can generalize their results to the approximate case:
we choose $b_{k}$, $\epsilon_{k}$, $\eta_{k}$ as in \Cref{thm:asj}, then we
get the same kind of bound as for ASJ, with difference only in the constants.
This result applies to both the smooth convex case and the smooth
nonconvex case, with the cost in the nonconvex case having the form of the
duality bound.

We consider the nonsmooth convex case, and give a stochastic version that has
error $\epsilon$ using $O(\epsilon^{-4})$ stochastic gradients and
$O(\epsilon^{-4})$ linear optimizations.
The algorithm aggregates past stochastic gradients to construct a proxy
$\bar{g}_{k} + \grad \Phi(w_{k})$ for the full gradient.
The component $\bar{g}_{k}$ is a weighted sum of the stochastic gradients from
past iterations.
The term $\grad \Phi(w_{k})$ has a regularizing effect of encouraging
alignment of $d$ with $w_{k} - w_1$ when $\Phi$ is strongly convex with
$\Phi(w_1) = 0$.
This is because
$\langle \grad \Phi(w) - \grad \Phi(w'), w - w' \rangle
\ge \rho \norm{w - w'}_2^2$.
Without loss of generality, assume $\Phi(w)$ is $\rho$-strongly convex and
1-smooth.
One possible choice of $\Phi$ is
$\Phi(w) = \frac{1}{2} \norm{w - w_1}_2^2$.

\begin{algorithm}[h!]
	\caption{Approximate Regularized Stochastic Frank Wolfe}
	\label{alg:arsfw}
	\begin{algorithmic}
		\State $w_1 \gets \argmin_{w \in W} \Phi(w)$.
		\State $\bar{g}_1 = 0$.
		\For{$k = 1, 2, \ldots$}
			\State Choose $d_{k} \in S$ such that
				$\left(\bar{g}_{k} + \grad \Phi(w_{k})\right)^{\top} d_{k}
				\le \min_{d \in S}
				\left(\bar{g}_{k} + \grad \Phi(w_{k})\right)^{\top} d + \epsilon_{k}$.
			\State $w_{k+1} = (1 - \eta_{k}) w_{k} + \eta_{k} d_{k}$.
			\State $\bar{g}_{k+1} = \bar{g}_{k} + \sigma_{k} g_{k}$, where
			$g_{k} = \grad f_{i_{k}}(w_{k})$ for random $i_{k}$ in $[n]$.
		\EndFor
	\end{algorithmic}
\end{algorithm}

A similar algorithm has been used in online learning by
\citet{hazan2012projection,hazan2016introduction}.
They used fixed instead of variable $\eta_{k}$, and they perform exact instead
of approximation minimization at each step.

\begin{thm} \label{thm:arsfw}
Let $\Phi(w)$ be a $\rho$-stronly convex 1-smooth function,
$R^2 = \max_{w \in W} \Phi(w) - \Phi(w_1)$,
$\eta_{k} = \frac{1}{k^{p}}$,
$\epsilon_{k} = \frac{(\lambda-1) R^2}{\rho} \eta_{k}$, and
$\sigma_{k} \le c \eta_{k}^{3/2}$, where $\lambda \ge 1$, $c > 0$ and
$p \in [0,1]$ are constants.
Assume $\norm{\grad f_i(w)}_2 \le L$ for all $i$ and $w$.
Let $\bar{w}_t = \sum_{k=1}^{t} \sigma_{k} w_{k} / \sum_{k=1}^{t} \sigma_{k}$,
	$K = \left(\sqrt{\frac{1}{2\rho}} \frac{cL}{1-p}
		+ \sqrt{\frac{\lambda R^2 + c^2 L^2}{\rho(1-p)}
		+ \frac{c^2 L^2}{2 \rho (1-p)^2}}\right)^2$,
then we have
\begin{align}
  {\mathbb E} f(\bar{w}_t) - f(w^*)
	\le
		\left(3L \sqrt{\frac{2K}{\rho}} + \frac{2c L^2}{\rho}\right)
		\frac{\sum_{k=1}^{t} \sigma_{k} \sqrt{\eta_{k}}}{\sum_{k=1}^{t} \sigma_{k}}
		+ \frac{R^2}{\sum_{k=1}^{t} \sigma_{k}}.
		\label{eq:rate1}
\end{align}
In particular, when $p = \frac{1}{2}$, for any $t \ge 1$,
\begin{align}
  {\mathbb E} f(\bar{w}_t) - f(w^*)
	\le
		\left(3L \sqrt{\frac{2K}{\rho}} + \frac{2c L^2}{\rho}\right)
		\frac{\ln t + 1}{t^{1/4}}
		+ \frac{R^2}{c t^{1/4}}.
		\label{eq:rate2}
\end{align}
In addition, if $\sigma_{k} = \sigma = \frac{c}{t^{3/4}}$, then
\begin{align}
  {\mathbb E} f(\bar{w}_t) - f(w^*)
	\le
		\left(4L \sqrt{\frac{2K}{\rho}} + \frac{8 c L^2}{3 \rho} + \frac{R^2}{c}\right)
		\frac{1}{t^{1/4}}.
		\label{eq:rate3}
\end{align}
\end{thm}

We state two lemmas and then prove this theorem.

\begin{restatable}{lem}{lemlazy} \label{lem:lazy}
Let $\Phi(w)$ be a $\rho$-strongly convex function,
$F_{k}(w) = \sum_{i=1}^{s-1} \sigma_i g_i^{\top} w + \Phi(w)$,
$w^*_{k} = \argmin_{w \in X} F_{k}(w)$,
$R^2 = \max_{w \in W} \Phi(w) - \Phi(w^*_1)$.
Then for any $w \in X$,
\begin{align*}
	\sum_{k=1}^{t} \sigma_{k} g_{k}^{\top} (w^*_{k} - w)
	\le \sum_{k=1}^{t} \frac{2 \sigma_{k}^2 \norm{g_{k}}_2^2}{\rho} + R^2.
\end{align*}
\end{restatable}

\begin{restatable}{lem}{lemsfwrecurrence} \label{lem:arsfw-recurrence}
Let $\eta_{k} = \frac{1}{k^{p}}$, and
$\sigma_{k} \le c \eta_{k}^{3/2}$, where $c$ is a positive constant, and $p$ a
positive constant in $(0,1)$.
Let $R$, $\rho$ and $L$ be positive constants, and $K$ as defined in
\Cref{thm:arsfw}.
If $e_1 \le K \eta_1$, and
\begin{align*}
  e_{k+1}
    &\le (1 - \eta_{k}) e_{k}
      + \frac{\lambda R^2}{\rho} \eta_{k}^2
			+ \sqrt{\frac{2}{\rho}} \sigma_{k} L \sqrt{e_{k+1}}, \numberthis\label{eq:e}
\end{align*}
then $e_{k} \le K \eta_{k}$ for any $k \ge 1$.
\end{restatable}

\begin{proof}[Proof of \Cref{thm:arsfw}]
Let $F_{k}(w) = \sum_{i=1}^{s-1} \sigma_i g_i^{\top} w + \Phi(w)$,
then $F_{k}$ is $\rho$-strongly convex and 1-smooth.
Let $w^*_{k} = \argmin_{w \in W} F_{k}(w)$,
$h_{k}(w) = f_{i_{k}}(w)$, and
$\tilde{h}_{k}(w) = h_{k}(w - (w^*_{k} - w_{k}))$.
Then we have
$g_{k} = \grad \tilde{h}_{k}(w^*_{k})$.
Using the convexity of $\tilde{h}$ and \Cref{lem:lazy}, we have
\begin{align*}
	\sum_{k=1}^{t} \sigma_{k} \left(\tilde{h}_{k}(w^*_{k}) - \tilde{h}_{k}(w^*)\right)

	\le \sum_{k=1}^{t} \sigma_{k} g_{k}^{\top} (w^*_{k} - w^*)

	\le \sum_{k=1}^{t} \frac{2 \sigma_{k}^2 \norm{g_{k}}_2^2}{\rho} + R^2.

\end{align*}
We have $|h_{k}(w) - \tilde{h}_{k}(w)| \le L \norm{w_{k} - w^*_{k}}_2$
for any $w \in W$ because $h_{k}$ is $L$-Lipschitz.
Hence
\begin{align*}
	\sum_{k=1}^{t} \sigma_{k} \left(h_{k}(w_{k}) - h_{k}(w^*)\right)
	&= \sum_{k=1}^{t} \sigma_{k} \left((h_{k}(w_{k}) - h_{k}(w^*_{k})) + h_{k}(w^*_{k}) - h_{k}(w^*)\right)\\
  &\le \sum_{k=1}^{t} \sigma_{k} \left(L \norm{w_{k} - w^*_{k}}_2
		+ (\tilde{h}_{k}(w^*_{k}) + \norm{w_{k} - w^*_{k}}_2)
	- (\tilde{h}_{k}(w^*) - \norm{w_{k} - w^*_{k}}_2)\right)\\

  &\le \sum_{k=1}^{t} \left(3L \sigma_{k} \norm{w_{k} - w^*_{k}}_2
		+ \frac{2 \sigma_{k}^2 L^2}{\rho}\right) + R^2.
\end{align*}
We have
$\frac{\rho}{2} \norm{w_{k} - w^*_{k}}_2^2
\le e_{k}
= F_{k}(w_{k}) - F_{k}(w^*_{k})$, because $F_{k}$ is
$\rho$-strongly convex.

Note that $\grad F_{k}(w_{k}) = g_{k} + \grad \Phi(w_{k})$,
thus $w_{k+1}$ is obtained by doing an $\frac{(\lambda - 1)R^2}{\rho}$-FW
step on $F_{k}$.
On the other hand $F_{k}$ has curvature at most $\frac{2 R^2}{\rho}$
because $F_{k}$ is 1-smooth, and
	$\norm{w - w'}_2^2
	\le \frac{2}{\rho}(\Phi(w) - \Phi(w'))
	\le \frac{2 R^2}{\rho}$
for any $w, w' \in W$ due to the $\rho$-strong convexity of $\Phi$.
Using \Cref{lem:approx-recurrence}, we have
$F_{k}(w_{k+1}) - F_{k}(w^*)
	\le (1 - \eta_{k}) e_{k} + \frac{\lambda R^2}{\rho} \eta_{k}^2$.
Thus we have
\begin{align*}
  e_{k+1}
    &= F_{k}(w_{k+1}) - F_{k}(w^*_{k+1})
      + \sigma_{k} g_{k} (w_{k+1} - w^*_{k+1}) \\
    &\le F_{k}(w_{k+1}) - F_{k}(w^*_{k})
      + \sigma_{k} L \norm{w_{k+1} - w^*_{k+1}}_2 \\
    &\le (1 - \eta_{k}) e_{k}
      + \frac{\lambda R^2}{\rho} \eta_{k}^2
			+ \sqrt{\frac{2}{\rho}} \sigma_{k} L \sqrt{e_{k+1}}.
\end{align*}
Using \Cref{lem:arsfw-recurrence}, we have $e_{k} \le K \eta_{k}$.
Thus $\norm{w_{k} - w_{k}^*}_2 \le \sqrt{\frac{2K}{\rho} \eta_{k}}$.
Hence we have
\begin{align*}
\sum_{k=1}^{t} \sigma_{k} (h_{k}(w_{k}) - h_{k}(w^*) )
	&\le \sum_{k=1}^{t} \left(3L \sigma_{k} \norm{w_{k} - w^*_{k}}_2
		+ \frac{2 \sigma_{k}^2 L^2}{\rho}\right) + R^2 \\
	&\le \sum_{k=1}^{t} \left(3L \sqrt{\frac{2K}{\rho}} \sigma_k \sqrt{\eta_{k}}
		+ \frac{2 c L^2}{\rho} \sigma_{k} \sqrt{\eta_k} \right)
		+ R^2.  \numberthis  \label{eq:a}
\end{align*}
We used the fact that
$\sigma_{k}^2
= \sigma_{k} c\eta_{k}^{3/2}
\le c \sigma_{k} \sqrt{\eta_{k}}$ in the last inequality.
Now observe that we have
\begin{align*}
	&\quad {\mathbb E} \left(\sum_{k=1}^{t} \sigma_{k} (h_{k}(w_{k}) - h_{k}(w^*))\right) \\
	&= \sum_{k=1}^{t} {\mathbb E}\left(\sigma_{k} (h_{k}(w_{k}) - h_{k}(w^*))\right)
	= \sum_{k=1}^{t} {\mathbb E}\left(\sigma_{k} (f(w_{k}) - f(w^*))\right) \\
	&= {\mathbb E}\left(\sum_{k=1}^{t} \sigma_{k} (f(w_{k}) - f(w^*))\right)
	\ge {\mathbb E}\left((\sum_{k=1}^{t} \sigma_{k}) (f(\bar{w}_t) - f(w^*))\right),
	\numberthis \label{eq:b}
\end{align*}
where the first equality holds due to linearity of expectation,
the second equality holds because we take expectation with respect to $i_{k}$ (but
not $w_{k}$),
the third equality holds due to linearity of expectation, and
the last inequality holds due to the convexity of $f$.
From \Cref{eq:a} and \Cref{eq:b}, we obtain \Cref{eq:rate1}.

When $p = \frac{1}{2}$, observe that
$\sum_{k=1}^{t} \sigma_{k}
= \sum_{k=1}^{t} c k^{-3/4}
\ge c t^{1/4}$,
$\sum_{k=1}^{t} \sigma_{k} \sqrt{\eta_{k}}
= \sum_{k=1}^{t} k^{-1}
\le \ln t +1$, then using \Cref{eq:rate1} we obtain \Cref{eq:rate2}.

When $\sigma_{k} = \sigma = c t^{-3/4}$,
using \Cref{eq:a} and \Cref{eq:b} and observe that
$\sum_{k=1}^{t} \sqrt{\eta_{k}} \le \frac{4}{3} t^{3/4}$, we obtain
\Cref{eq:rate3}.
\end{proof}

\section{Conclusion}
We have given a unified analysis of two approximate greedy algorithms, and
presented new results on convergence and their connections.
In addition, we studied their stochastic versions and demonstrated these
algorithms can be robust against the optimization error in each iteration.

There are a few questions for further exploration.
From recent results in FW and the equivalence result in \Cref{thm:equiv},
it is natural to ask whether Jones' algorithm converges at faster rates under
suitable additional assumptions, and whether more efficient stochastic Jones'
algorithm can be obtained.
For stochastic FW, the nonsmooth case seems to be harder than the smooth case.
Results on complexity lower bounds will lead to better understanding on the
greedy algorithms and these problems.

\newpage
{\footnotesize
\bibliographystyle{plainnat}


text:
Audubons pijlstormvogel (Puffinus lherminieri) is een vogel uit de familie van de stormvogels en pijlstormvogels (Procellariidae). Over de indeling van deze soort in soorten en ondersoorten bestaat geen consensus. Op de IOC World Bird List  staan soorten die voor 2005 vaak nog als ondersoorten werden beschouwd. Deze vogel is genoemd naar de bekende ornitholoog en illustrator John James Audubon.

Kenmerken
De vogel is 27 tot 33 cm lang en weegt 138 tot 290 gram en heeft een spanwijdte van 64 tot 74 cm. Het is een vrij kleine pijlstormvogel die van boven egaal zwartbruin of donkergrijs, soms met wat wit om het oog. De vogel is van onder wit met op de flanken van de buik bruingrijs dat niet zo scherp is afgescheiden van het wit. De vleugels zijn relatief kort en breed  en de staart is vrij lang en afgerond.

Verspreiding en leefgebied
Deze soort telt twee ondersoorten:
 P. l. lherminieri: West-Indië. Dit is de nationale vogel van Saba.
 P. l. loyemilleri: de eilandjes nabij Panama in de zuidwestelijke Caraïbische Zee.

Deze zeevogels broeden op rotsige eilanden waar ze holen graven in spaarzaam met gras begroeide hellingen of nestelen in rotsspleten, vaak in kolonies.

Status
De grootte van de wereldpopulatie werd in 2017 geschat tussen de 30 en 59 duizend volwassen individuen. De aantallen gaan achteruit; echter, het tempo ligt onder de 30% in tien jaar (minder dan 3,5% per jaar). Om deze redenen staat Audubons pijlstormvogel als niet bedreigd op de Rode Lijst van de IUCN.

Stormvogels
IUCN-status niet bedreigd
Dier uit het Neotropisch gebied

redpajama_set_name: RedPajamaWikipedia


text:
Coach Mo addresses media after loss at Tulsa
by: Brian Bailey
GREENVILLE, N.C.(WNCT) – First-year East Carolina University Head Football Coach Scottie Montgomery addressed members of the media on Monday prior to this Saturday's home game against SMU. The following are selected comments:Opening Statement:
"I'll start by saying Tulsa had a great team with a lot of weapons on offense and a lot of weapons on defense. Offensively, their weapons were their skill players – the receivers, the backs – and all of them combined proved to be a tough task for our defense. On defense, I thought their skill was at the defensive end position. It really gave us a hard time by rushing three at times and even rushing four gave us some hard challenges. They won this game at the line of scrimmage. I thought their run game, in every facet, was superior to ours in the way that we executed and the way that they executed. They were able to create pressure with four and sometimes three (pass-rushers), which allowed their team to use a lot of coverage's against our quarterbacks. On the other hand, I thought we could only apply pressure by bringing six or seven, which put way too much pressure on our cover guys. We've got a lot of growing to do in both cases.
"Congratulations to Zay Jones on another great performance. I also thought Gardner (Minshew) did a great job coming into the game in some situations where he was able to scramble forward and make plays. Also, I thought defensively, Kiante Anderson played with a lot of grit. He played with a chip, which I'd like to see a lot more of our guys play with at this point in time of the season. Special teams also provided a plus on several occasions. That's something we have grown week-to-week. I'm very proud of the way they put their plan together this past Saturday.
"We've got a lot of growing to do as a team. I think we have to continue to give our guys the best opportunity to win every single situation and play. We're working very, very hard to make sure we do that."On What More The Team Can Do To Win:
"The first thing we have to do is eliminate the things that we haven't had before. The penalties have to go away. I think our technique in coverage and tackling has to be a lot better. We're trying to put as many different guys and bodies on the field that we can. The first thing you have to do is control all of the things that take no physical talent, and that's what we'll start with."On How Close Gardner Minshew Was To Starting Saturday's Game At Tulsa:
"We were close. It came down to Philip having a really good Friday. Moving forward, we'll be in a similar situation. He's going to have to be able to practice to go, especially with the performance Gardner had. He's been good every time that he's come in from a percentage standpoint, but also the timing of everything that we're doing. If Friday had been different, we probably would have had a different starter."On What He's Learned About Gardner Minshew After Seeing Him Play A Few Games:
"Pocket poise is the biggest thing. Right now, we're going to have to have a lot of pocket poise. Coming into the season, we knew (we had) offensive line limitations, but it's not always going to be clean. There's not always going to be an umbrella in the pocket. The guy that can be poised and step up into the pocket, as bad as that may sound, and create some scrambling toward the line of scrimmage is going to have a better opportunity. We've seen Gardner do a good job of that."On If Zay Jones Is Aware With All Of The Numbers He's Accumulating:
"I think he's working to try to win every game. That's not his deal. If it was someone else on the team I would probably say they were pretty conscious of it, just like if another receiver out there was close to it. I don't know if they could handle it the way he has. He's more concerned about our wins and losses. When it comes, it'll be a big deal for him and we'll make sure we celebrate it, but the biggest deal is he's trying to lead in every single way that he can. That's what he's focused on."On What Stands Out On SMU's Team:
"Tremendous growth and skill at the receiver position. I don't mean all over like I did last week, but I think (Courtland) Sutton is probably one of the biggest, strongest players that we've seen at the position. He's an extreme talent. All around, they play hard. Defensively, they get to the football. They've created a lot of opportunities to be in winning situations at the end of games. Their record may not display how close they've been. I think this last week was just an anomaly. You see certain games where things don't go your way early, and I think that's what happened to them. They had a few turnovers where things go wrong, but I think the competitive nature that Coach (Chad Morris) has been able to instill in his team in their second year has been easy to see."On His Involvement With Tony Petersen's Offensive Play-Calling:
"I'm very involved. I've spent a lot of time in there. If you told me at the beginning of the year that we'd average 500 yards per game, I would have been okay. Then, you tell me we only score 28 points per game and I would have been pressed because we like to be in the 32-point range and we're not there. The biggest point is our red zone performance has been getting better and better. Unfortunately, this past week we had a red zone opportunity that was marred with back-to-back mental errors. When you put a scheme together and you feel like you have the perfect scheme and the perfect play-call and everything, and we have a mental error inside of that where we've had them a couple times down there in the red zone. But when we got the ball where we wanted to get it, especially when I talk about getting the ball inside the five (yard line) and first down or inside the three, (that can't happen) in those situations. We've got to continue to grow, but we still have a long way to go."On The Significance Of Military Appreciation Day This Coming Saturday:
"I can't say enough about our military and what they do for the United States of America. I'm proud to be an American. I can remember waking up on September 11. I was in Denver, Colorado and saw our service people. I remember waking up again a year or two later and seeing people I knew really well, grew up with, went to high school with or was in college with being deployed or getting ready to go fight for the right of all of us to do everything that makes America great. There is something special, not only from me, but my entire family because of the way I was raised and the people I've been around – the pride and heart that goes into saying that I will do anything for people that I don't even know and stand on the line and put your life in the middle of true fire for the freedoms of people you don't know. I also have been a part of knowing Pat Tillman and understanding what he had to go through to come to his thought pattern. I've played in the National Football League. I've had all the things in life you could possibly imagine being given to you, and for him to go represent us and every other young man and woman that has gone across the seas, I'm very thankful for what they do and how much they sacrifice not only for me, but my children and hopefully one day, my children's children."On Thoughts After Making The Quarterback Change And How Long Of A Leash Philip Nelson Had:
"I don't think it was short. If you watch early parts of the game, I thought we just missed some throws. A lot of people thought they were down-the-field throws, but they weren't. We missed some hitches where Zay had to go down to get it and fell down. Those plays turn into second-and-one, and then it gives a play-caller the whole playbook. Instead, we were second-and-six, and I saw some of those. Then we had some times where the pocket did break down. I would've liked to see him scramble toward the line of scrimmage and throw the ball away rather than retreat and take sacks. Those were some of the critical times that I thought some of it had to do with his physical ailment."
by Ariana Kraft / Jan 20, 2021
GREENVILLE, N.C. (WNCT) - President Biden is already getting to work just hours after taking office. He's expected to make immediate changes to federal policies through lots of executive orders.
Some people say they are hopeful about the new president, while some have their doubts.
by Jason O. Boyd / Jan 20, 2021
BEAUFORT, N.C. (WNCT) -- Three people were arrested on Jan. 14 after a drug investigation around the distribution of meth in and around Eastern North Carolina.
Lee Quinn Graham, 30, of Jacksonville, Jamie Devon Fox, 27, of Fayetteville, and Hannah Jane Stewart, 20, of Jacksonville, were taken into custody and were charged at a parking lot in Cedar Point. The three each face three counts of trafficking in methamphetamine and one count ofconspiring to traffic methamphetamine. Graham and Fox, both convicted felons, also face weapons counts for possession of a firearm by a felon.
WASHINGTON, D.C. (WNCT) -- Congressmen Greg Murphy and G.K. Butterfield congratulated President Joe Biden on taking the oath of office on Wednesday.
Murphy could not attend Wednesday's inauguration due to his wife's recent surgery. Instead, he issued a press release about the ceremony and his thoughts moving forward.
Vehicle stop leads to Greenville man arrest

redpajama_set_name: RedPajamaCommonCrawl


We are pleased to welcome Rachael Hanak, Rita Grant, and Rosellen Gemino to Cover & Rossiter.
Hanak joined the tax department in July as a staff accountant. She graduated last May from Widener University with a Bachelor's of Science in Accounting and a minor in Tax. She was an active member in the Honors Program and General Education and School of Business Administration Honors Program. Hanak interned at Cover & Rossiter in spring 2017 and at Wipfli LLP in summer 2017. When she's not working, Hanak loves to read and travel with her family.
Grant joined the tax department in August as a staff accountant. She graduated in May with a Bachelor's of Science in Accounting from West Chester University. Grant interned at Cover & Rossiter this past spring and, prior to that, worked as an intern in finance and accounts receivable for Wesco Aircraft. She was involved in many clubs and activities at WCU and was co-founder and president of the West Chester University Irish Dance Team. During her free time, Grant likes to teach dance classes, travel, and spend time with family and friends.
Gemino joined our administrative staff in June and is the first face you see when you walk into the firm. After leaving New York, where she was born and raised, she retired briefly while living in southern Delaware. Her past experience includes working as an office manager/bookkeeper at Profile Technologies, Inc., and working in Corporate Cash Management for Oppenheimer & Co., Inc. Gemino and her husband, Henry, are empty nesters while their daughter teaches special education in Brooklyn, New York, and their son studies medicine in Philadelphia. As members of Winterthur, they continue their interest in the arts and visit the superb house and gardens on a regular basis.


Wann wird look, see und wann watch verwendet?
look sich etwas genau ansehen Look at the board, please.
nachsehen/nachschlagen (z.B. Wörterbuch) You can look up the words in the dictionary.
see etwas wahrnehmen Can you see the blue car over there?
verstehen I see what you mean.
zuschauen, beobachten He watches TV in the evenings.


Haden Kirkpatrick is the head of marketing strategy and innovation at Esurance. Haden is a futurist who is constantly thinking about how IoT, blockchain and machine learning will impact the insurance industry. He writes for a variety of publications on innovations in home and auto insurance.
How Is New Technology Disrupting Insurance?


text:
Асія Д'Амато (;  7 лютого 2003, Генуя, Італія) — італійська гімнастка. Призерка чемпіонату світу в опорному стрибку та в команді.

Біографія
Має сестру-близнючку Алісу, яка також займається гімнастикою. Відвідувала секцію акробатичних танців, де тренер порекомендував спробувати спортивну гімнастику.

Спортивна кар'єра
Тренується в Міжнародній академії в Брешія, Італія, у Енріко Каселло, Моніки Бергамеллі, Марко Камподоніко.

2019
У квітні на чемпіонаті Європи у фіналі в опорному стрибку посіла четверте місце.

На дебютному чемпіонаті світу в Штутгарті, Німеччина, разом з Дезіре Карофігліо, Елісою Іоріо, Джорджією Вілла та сестрою Алісою Д'Амато в командних змаганнях сенсаційно здобули бронзові нагороди, що стало повторенням найкращого результату італійської збірної в командних змаганнях з чемпіонату світу 1950 року, крім того, здобули командну олімпійську ліцензію на Олімпійські ігри 2020 у Токіо, Японія. До фіналів в окремих видах не кваліфікувалась.

Результати на турнірах

Примітки

Італійські гімнасти
Гімнасти на літніх Олімпійських іграх 2020


Sitrus berries are special berries that have healing powers for your Pokémon. This plush sitrus berry wrist accessory is the perfect size for your furry friend! © 2017 Pokémon. © 1995–2017 Nintendo/Creatures Inc./GAME FREAK Inc. TM, ©, and character names are trademarks of Nintendo.


text:
Schools & Universities in Ireland
Online Schools & Universities in Ireland
The Institute Of Education
Irish Bible Institute
Bachelors in Ireland
BScs in Ireland
BAs in Ireland
Universities in Ireland
What Does Christmas Look Like on University Campuses Around the World?
"Silent night, holy night, all is calm, all is bright" -- these song lyrics ring out in different languages around the world during this spe...
Six Things To Know About Studying in Ireland
Ireland may conjure images of rolling green hills, rural cottages, dramatic cliffs, and even shamrocks, but it's also a popular choice for i...


KPM late 18th Century Boy and Girl Porcelain Figurines: KPM late 18th Century Boy and Girl Porcelain Figurines: Measure 6" tall, with blue staff mark. White base and gold line at base. Boy holding a bird's nest, girl holding basket.


text:
Ozanam House, St. Augustine Street Galway H91 V3PV
Monday-Friday: 9am to 5pm / Saturday / Sunday: Closed
History Of Sexual Health West
Information Service & Drop In
STI Information
Post Exposure Prophylaxis
Undetectable Equals Untransmittable (U=U)
Condoms And Lubricant
Key Facts About HIV
How Can You Get HIV?
STI Clinics: Galway And Mayo
Crisis Sexual Health – Sexual Assault & Crisis Pregnancy
HIV Supports in Ireland and UK
STIs and Testing Options
LGBTQI+ Support
Mental Health, Youth and Intimate Violence supports
Other Helplines
All Local Supports
Home - STI Information
The STI information that is listed under the sexually transmitted infections section of our website is gathered from reputable medical sources and is updated on a regular basis. If you are worried about any aspect of your sexual health, contact your GP or local sexual health clinic.
The intention of this brief introduction is to inform you about the possible risks associated with unprotected sexual intercourse. It is not intended to dissuade you from having positive sexual relationships.
Getting an STI is nothing to be ashamed of. The risk of STIs is part of the reality of being sexually active. It is important to be able to talk openly about STIs as we would any other infection or illness, free from shame. It is essenital that sexually active people get tested regularly, get treated, use barrier protection during all kinds of sex (condoms or dental dams), communicate with sexual partners, never disclose someone elses's STI status and reject STI stigma!
Sexually transmitted infections (STIs) are common in Irish society today. All STIs can be treated, and most can be cured. Though most of them are easily treated, there are some that may need more extensive treatment.
The main STIs are divided into two categories – bacterial and viral. Bacterial infections are easily treated with a course of antibiotics if detected at an early stage. Viral infections can be treated with anti-viral medication but in some instances cannot be eradicated from the system.
It is important to note that using a condom during sexual intercourse will not give you 100% protection against STIs/HIV, but it will greatly reduce the risk of contracting an infection.
STI Symptoms
Itching around the vagina and/or discharge from the vagina for women
Discharge from the penis for men
Pain during sex or when urinating
Pain in the pelvic area
Sore throats in people who have oral sex
Pain in or around the anus for people who have anal sex
Chancre sores (painless red sores) on the genital area, anus, tongue and/or throat
A scaly rash on the palms of your hands and the soles of your feet
Dark urine, loose, light-coloured stools, and yellow eyes and skin
Small blisters that turn into scabs on the genital area
Swollen glands, fever and body aches
Unusual infections, unexplained fatigue, night sweats and weight loss
Soft, flesh-coloured warts around the genital area
Bacterial Vaginosis (BV) is caused by an imbalance of the normal bacteria in the vagina and symptoms can include a watery discharge sometimes with a fishy smell. It can be more noticable after sex or during the menstrual period. Although it is not a sexually transmitted infection, symptoms can be similar to some STIs. Diagnosis is made by a swab taken from the genital area, and if isolated it is easily treated by antibiotics or a cream inserted into the vagina. Men are generally not affected by BV and there is no evidence to suggest that treating male partners is helpful. A common cause of the condition is washing or douching the vaginal area with perfumed soaps or shower gels which are best avoided.
Candida or thrush is caused by a yeast fungus which can be found in the vagina, mouth, anus and sometimes the head of the penis. Occasionally the yeast multiplies rapidly and can cause symptoms.
Itching, soreness and redness around the vaginal area. A thick, white discharge from the vagina, swollen vulval area and discomfort when having sex.
Redness and burning at the tip of the penis, red patches under the foreskin or on the head of the penis.
Thrush should be initially diagnosed by a doctor to exclude any sexually transmitted infections. If there are no symptoms it is harmless so does not need to be treated. When treatment is called for it can be bought at a pharmacy and includes pessaries, tablets or creams.
Avoid perfumed soaps and vaginal deodorants. Wash and wipe from front to back to avoid spreading yeast from anus to vagina. Wear cotton underwear and avoid wearing restrictive clothing such as tight jeans/trousers, nylon underwear and tights.
Chlamydia is caused by a bacterium and is one of the most common sexually transmitted infections in Ireland. About half of all men and three-quarters of all women who have chlamydia have no symptoms and do not know that they are infected.
When symptoms do occur in women they include unusual vaginal bleeding or discharge, pain in the abdomen, painful sexual intercourse, fever, painful urination or the urge to urinate more frequently than usual. Men may get yellow, green or white discharge from the end of the penis. They may also have pain while passing urine. Chlamydia in men can sometimes spread into the testicles causing pain and inflammation.
Untreated chlamydia in women can lead to pelvic inflammatory disease (PID), an infection of the uterus, fallopian tubes, and/or ovaries. PID can cause scarring inside the reproductive organs and can lead to infertility. Women may also pass on chlamydia to their babies during childbirth, which can result in an eye infection in the baby. The test for chlamydia may be performed on swab specimens collected from the cervix (women) or urethra (men).
Chlamydia infection can be easily and effectively treated with antibiotics. Sexual partners need treatment. Sex, even with condoms, should be avoided until all sexual partners are adequately treated.
Using a condom correctly during every sexual encounter can lower the risk of contracting chlamydia
Herpes simplex virus (HSV) is a virus that is spread through direct skin contact during sexual activity. There are two types of the herpes virus, HSV 1 which more commonly affects the mouth and is known as a 'cold sore' and HSV2 which usually causes sores around the genital area. When there are no symptoms, HSV lies dormant in the nerve cells, replicating just under the skin during an outbreak.
HSV is generally transmitted by direct contact of lips and /or genitals when the sores are present, or just before they appear. The first outbreak after exposure to HSV is commonly more severe than future outbreaks, as initially, the immune system has not had a chance to produce antibodies. Some people feel generally unwell and have flu-like symptoms with the first attack, they may also complain of swollen glands in the groin area. Outbreaks are generally preceded by sensations of burning, itching or tingling before visible blistering occurs. The virus is most likely to be passed on through skin-to-skin contact when the symptoms of ulcers or blisters are present. However, occasionally the virus can be shed and passed on without there being signs or symptoms. This is called viral shedding.
It is very important that pregnant women who have the first attack of HSV during pregnancy inform their doctor or midwife, as it is possible for women to pass on the virus to their baby during childbirth.
There is no known cure or vaccine for HSV. Treatment is available in the form of antiviral medication which reduces the duration of symptoms and accelerates healing. For best results, treatment should begin at the first signs of an outbreak. If treatment begins before the lesion appears, it is possible that the outbreak can be averted.
Another option for people who experience very frequent outbreaks is the use of daily suppressive therapy, in which antiviral tablets are taken every day. Suppressive therapy reduces the frequency of symptoms and recurrence of outbreaks. In addition, suppressive therapy reduces viral shedding, lowering the risk of transmission through sexual contact or kissing.
Genital warts are Ireland's most common sexually transmitted infection caused by the human papillomavirus (HPV). The virus is spread through skin-to-skin contact, during genital or anal sex.
Other strains of HPV are associated with 90% of cervical cancer. However, the HPV strains responsible for this differ from the strains that cause genital warts.
Genital warts are painless growths that may be found around the genital or anal area. The period of time from infection to displaying symptoms can be anywhere from 3 to 12 months. The warts can occur individually or in a cluster. In women, warts can occur either outside or inside of the vagina, on the opening to the womb (cervix) or around the anus. In men, the symptoms are usually seen on the tip or shaft of the penis, on the scrotum, or around the anus.
Depending on the location and size of warts, a doctor will decide on the best method of treatment. A topical cream can be applied to the affected area or in the case of small warts they can be removed under medical supervision by freezing, burning or laser treatment. Surgery is occasionally used to remove large warts that have not responded to other treatment.
The virus that causes genital warts is spread by skin-to-skin contact. Because the warts may be located around the anal or genital area, using a condom cannot guarantee 100% protection, though it greatly reduces the risks if the warts are located on the tip of the penis or inside the vagina.
Pregnancy & Childbirth:
Women who are pregnant may have trouble getting rid of the warts during their pregnancy, but find they often disappear on their own after the baby is born. The warts do not usually cause any harm to the baby.
GONORRHEA "The Clap"
Gonorrhoea is a bacterial infection that is easily transmitted through sexual contact, including oral sex. The incubation period varies from 2 to 14 days, with most symptoms occurring between days 2 and 5 after being infected. A small number of people may have no symptoms.
Between 30-60% of women with gonorrhoea have no symptoms. Women with symptoms may complain of vaginal discharge, difficulty urinating, bleeding between periods, or bleeding after sexual intercourse. More advanced symptoms, which may indicate the development of pelvic inflammatory disease (PID) include abdominal pain, vomiting or fever.
Most men who have the infection in the penis will notice symptoms. These might include pain on urinating like 'peeing broken glass' and thick green or yellow discharge. Symptoms may appear two to five days after infection but can take as long as 30 days to appear. Sometimes men with gonorrhoea get painful or swollen testicles. Gonorrhoea can also be found in the throat and rectum but usually without symptoms in these areas.
Doctors will usually use cervical swabs in women and urethral swabs in men to detect the presence of the bacterium.
The infection can be easily treated with a course of antibiotics. It is important to refer all sexual partners to be checked for gonorrhoea to prevent spread of the infection and to prevent re-infection. Sexual contact should be avoided, even with condoms, until all sexual partners are adequately treated.
Gonorrhoea is an STI. Proper use of barrier contraceptives such as condoms will significantly reduce the risk of getting gonorrhoea and its complications. However, this does not totally eliminate risk.
Hepatitis A is a viral infection transmitted by the faecal contamination of food and water. It causes an acute form of hepatitis (inflammation of the liver), does not have a chronic stage, and will not cause any permanent damage to the liver. It is not usually sexually transmitted, though outbreaks have been reported in gay and bisexual men. Once recovered it is not possible to pass it on. A vaccine is available that will prevent infection from Hepatitis A and it is recommended when travelling to countries with high levels of the infection, or those who may be at risk from sexual exposure such as gay or bi-sexual men.
These may include jaundice, dark urine, nausea, fever, fatigue, loss of appetite, stomach ache, vomiting.
The diagnosis of the virus is made through medical examination and blood tests.
There is no specific treatment for Hepatitis A. Those infected are advised to rest, avoid fatty foods and alcohol. They are also advised to eat a well-balanced diet and stay hydrated.
Hepatitis A can be prevented by vaccination to those at risk as well as following advice regarding food and water consumption when travelling to countries of high risk.
Hepatitis B is a virus that affects the liver and is one hundred times more infectious than HIV.
It is largely transmitted through exposure to bodily fluids containing the virus. This includes unprotected sexual contact, blood transfusions, re-use of contaminated needles and syringes as well as transmission from mother-to-child during childbirth.
Hepatitis B may either be acute (short-lived) or chronic (long-lasting). Individuals with acute infection may clear the virus spontaneously within weeks to months. More than 90% of adults who become infected will stage a full recovery and develop protective immunity to the virus.
Acute infection with Hepatitis B virus can begin with general ill-health, loss of appetite, nausea, vomiting, body aches, mild fever, dark urine, and then progresses to the development of jaundice. The illness lasts for a few weeks and then gradually improves in most of the affected people. The infection may also be entirely asymptomatic (without symptoms) and may go unrecognised.
Diagnosis is made through blood tests.
There are currently several treatments for chronic Hepatitis B that can increase a person's chance of clearing the infection. Treatments are available in the form of anti-virals. In general the medication works by reducing the viral load, thus helping the bodies immune system clear the infection.
Chronic carriers should be strongly encouraged to avoid consuming alcohol as it increases their risk of cirrhosis and liver cancer.
A preventative vaccine is available and is recommended to anyone who may be at risk of exposure. The vaccination is highly effective and consists of three injections usually given over a period of six months. Many countries now routinely vaccinate infants against Hepatitis B. In many areas, vaccination against Hepatitis B is also required for all healthcare workers. As higher levels of Hepatitis B are found in gay and bisexual men, vaccination is also recommended for this group. Using condoms during sexual intercourse will also reduce the risk of infection.
Hepatitis C (HCV) is a viral infection of the liver. The infection can cause liver inflammation that is often asymptomatic (without symptoms) but chronic hepatitis can result in cirrhosis and liver cancer. Hepatitis C is spread by blood-to-blood contact with an infected person.
Symptoms of acute Hepatitis C include fatigue, decreased appetite, abdominal pain, jaundice, itching, and flu-like symptoms.
HCV is diagnosed via a blood test but it can take up to six months for the body to develop antibodies to the virus that can be detcted in the blood, therefore tests should be repeated 6 months after possible exposure to get an accurate result.
The virus can be spread by blood to blood contact with an infected person. A common route is through injecting drugs and sharing the equipment used, such as needles, cookers, cotton, spoons, water, etc. Researchers have suggested that the transmission of HCV may be possible through the snorting of illegal drugs such as cocaine and crack when straws (containing even trace elements of mucous and blood) are shared among users. It is to be noted that the virus can survive up to six months outside the body. It can also be spread via inadequately sterilised medical, dental or tattooing equipment. Though no longer a problem in Ireland, blood products in other countries that have not been screened may pose a hazard.
Occupational Exposure to Blood
Medical and dental personnel can be exposed to HCV through accidental exposure to blood, through needlestick injuries or blood splashes to the eyes. Follow Universal precautions to protect against such accidental exposures which significantly reduce the risk of exposure to HCV.
Sexual Transmission
Transmission can occur during unprotected sexual contact if the sexual activity involves blood-to-blood contact.
Shared Personal Items
Though a low risk, for general hygiene reasons it is not advisable to share personal items such as razors, toothbrushes, cuticle scissors.
HCV is not spread through casual contact such as hugging, kissing, or sharing eating/cooking utensils.
Mother to Child Transmission
HCV can be transmitted from an infected mother to her child during the birth process. The risk of transmission in this setting is approximately 6 out of 100.
Human Immunodeficiency Virus (HIV) is a virus that affects the immune system. AIDS (Acquired Immune Deficiency Syndrome) is a less commonly used term to describe when HIV infection is advanced and has impacted the immune system to a significant level. This leaves the affected person open to certain illnesses known as opportunistic infections. Opportunistic infections are caused by organisms that usually don't affect people with a healthy immune system. If there has been any risk of exposure to HIV, it is better to be tested sooner rather than later. New treatments, when used at the right time, can prevent or delay AIDS.
How can I get HIV?
The most widely recognised ways of acquiring HIV are:
Having vaginal, anal or oral sex without a condom with someone who is HIV positive.
Sharing needles, syringes or other drug-injecting equipment with someone who is infected with HIV.
An HIV positive mother to her baby during pregnancy, delivery or while breastfeeding.
Blood transfusions, blood products or organ transplants in countries where screening is not mandatory.
Tattooing and/or piercing with improperly sterilised equipment.
A needle stick injury involving blood infected with HIV.
You cannot get HIV through:
Kissing, touching, hugging or shaking hands.
Coughing or sneezing.
Sharing cutlery or cooking utensils.
Eating food prepared by someone with HIV.
Swimming pools.
Insect or animal bites.
Contact with toilet seats.
Sexual route:
The majority of HIV infections are acquired through unprotected sexual intercourse. An HIV positive person can pass the virus on to someone else if they have vaginal or anal sex without a condom. Though oral sex is a lower risk of transmission, it is still possible to become infected via this route.
Blood or blood product route:
This transmission route can account for infections in intravenous drug users, haemophiliacs and recipients of blood transfusions (though most transfusions are checked for HIV in the developed world) and blood products. It is also of concern for persons receiving medical care in regions where sterilisation of equipment is inadequate. People who give and receive tattoos and piercings can also be at risk of infection where sterilisation procedures are not adhered to.
Mother-to-child transmission (MTCT):
The transmission of the virus from the mother to the child can occur in the womb and during childbirth. In the absence of treatment, the transmission rate between the mother and child is 25%. However, where drug treatment and monitoring are available, this can be reduced to 1%. Breastfeeding also presents a risk of infection for the baby.
HIV Test:
Many people are unaware that they are infected with HIV. HIV testing consists of a simple blood test, although it may take up to three months from catching the infection before the test shows a positive result. This is known as the 'window period'. If an HIV negative result is given it means the individual does not have HIV. If an HIV positive result is given, it means the individual has been infected with the virus. Every HIV positive result is rechecked to ensure it is accurate.
Due to medical advances, treatment for HIV in developed countries has led to an increased lifespan, but there is currently no vaccine or cure for HIV. The only known method of prevention is to avoid exposure to the virus. HIV treatment does not cure HIV, but it stops the virus from reproducing in your body. It can reduce the amount of virus in the blood to undetectable levels, meaning that you cannot pass on HIV. Treatment with anti-HIV drugs is sometimes called combination therapy because people usually take three different drugs at the same time – often combined into one tablet. It's also known as antiretroviral therapy (ART), or highly active antiretroviral therapy – HAART for short.
Using a condom correctly each time you have sexual intercourse will significantly reduce the risk. If there is concern about HIV, it is advisable for both partners to be tested and to ensure that the window period is covered before having unprotected sex. This will only protect against HIV in a monogamous relationship.
Please check out the video on.. HOW COULD I GET HIV? for more information.
PUBLIC LICE 'CRABS'
The pubic louse is a small insect that can live in almost any form of human hair. It can be found in eyebrows, eyelashes, beards, moustaches and even underarm hair, but is found most commonly in pubic hair. Although most commonly passed from direct body-to-body contact, the individual louse can survive for about 24 hours apart from its human host and therefore can be passed on in sleeping bags and bedding. The louse feeds on blood and can leave irritating spots on the skin. Though irritating, it is harmless.
The female louse lays eggs which stick to the body hair, are oval in shape and usually yellow to white, these are called nits. The adult pubic louse resembles a miniature crab when viewed through a strong magnifying glass and this is how the infection got the nickname "crabs." Pubic lice are tan to greyish-white in colour.
Treatment is simple and involves the application of a cream or lotion. Because lice can survive in bedding and clothing, these items must be washed before reuse. Sexual partners should also be treated to avoid reinfection.
Non-specific urethritis (NSU) is an inflammation of the urethra (the tube that leads from the bladder to the tip of the penis) and occurs in men.
The symptoms of urethritis can include pain or a burning sensation on passing urine, a white cloudy discharge and the urge to pass urine more frequently. However there are often no symptoms.
Urethritis can be caused by a number of organisms including gonorrhoea, chlamydia, trichomonas, herpes and candida. It is important to note that NSU can also be triggered by a number of non-infectious causes, including urethral stricture, foreign bodies, trauma, and various allergic conditions. Other causes may include physical damage, e.g. very vigorous sex or squeezing or chemical irritation from disinfectants.
Because of the number of different causes, treatment involves using a broad range antibiotic. It is important that sexual partners are also given antibiotics, and that sexual contact is avoided, even with condoms, until all partners are adequately treated. Women who are infected by their partner with NSU may develop pelvic inflammatory disease. If left untreated, complications may include infertility. Consistent and correct use of a condom during sexual intercourse greatly reduces the risk of infection.
Syphilis is a sexually transmitted infection caused by a bacterium called Treponema pallidum. Syphilis can be treated with penicillin or other antibiotics. If not treated, syphilis can cause serious medical problems such as damage to the nervous system, heart, or brain. Untreated syphilis can be fatal.
Stages Of Syphilis:
Primary Syphilis:
About 50% of people who have syphilis will have no symptoms at all. Someone with syphilis can be infectious to others for up to 2 years without appearing to show any symptoms. If symptoms do occur the first sign is a sore called a chancre. It is usually painless and located at the point of initial exposure to the bacteria. It is often on the penis, vagina or rectum. Local lymph node swelling may occur. The primary lesion may persist for 4 – 6 weeks and then heal spontaneously.
Secondary Syphilis:
Without treatment, the infection develops into the secondary stage. It is characterized by a skin rash that appears 1-6 months (average 6-8 weeks) after primary infection. This is a reddish-pink non-itchy rash on the trunk and extremities, which may involve the palms of the hands and soles of the feet. Other symptoms common at this stage include fever, sore throat, malaise, weight loss, headache and enlarged lymph nodes.
Tertiary Syphilis:
Untreated infection can lead to tertiary syphilis. This stage can remain asymptomatic for many years but those affected may develop a number of serious illnesses affecting the brain, heart, bones, liver and eyes.
The first choice of treatment for primary, secondary and early latent infections remains penicillin. There are alternative antibiotics available for those allergic to penicillin. It is important that any sexual partners are tested and treated to avoid re-infection and that sexual contact is avoided until everyone involved is treated. Using condoms will reduce the risk.
Avoidance of sexual contact with an infected person is the only completely reliable method of prevention. Regular screening for those at risk is advisable. Using condoms every time you have sexual intercourse will reduce the risk. All women in Ireland are offered a blood test at ante-natal appointments to ensure they do not have the infection, as it could be passed on to their unborn baby.
Trichomonas vaginalis is neither bacterial nor viral but actually a tiny parasite found in the vagina and urethra of women. The majority of men are asymptomatic but can carry and pass on the infection.
Women may not have any symptoms but if they do they may include greenish-yellow frothy discharge, itching and irritation.
Trichomonas vaginalis can be detected from a vaginal swab in women but can be hard to isolate in men.
Condoms will reduce the risk of infection.
The infection can be easily treated with antibiotics. Sexual partners should also be treated to prevent re-infection.
Are We In Or Are We Out?! The Current State Of Relationships And Sexuality Education In Ireland 2020
Are The Kids All Right?
Logged On, Turned On: Having Safe Cyber Sex In A Socially-Distanced World
Sexual Health West provides a free bi-annual newsletter titled "Happiness is Vital" to all its HIV positive clients, GPs, hospitals and health centres. If you would like to receive a copy of the newsletter, add your email address below.
Main Office: Galway, Ireland Call Us: +353 (0)91 566266 Email: info@sexualhealthwest.ie
© 2022 WISER | Privacy Policy | Cookie Policy | Contact Us | Web Design by Simple Sites


According to the Smith County District Attorney's Office, on Thursday, a Smith County jury found Anton Stewart Jr., 26, of Chandler, guilty of possession with the intent to deliver a controlled substance.
SMITH COUNTY, Texas — An East Texas drug dealer has been sentenced to 45 years in prison.
Evidence at trial revealed after a traffic stop and search of the Stewart's vehicle, he was in the possession of approximately seven grams of methamphetamine, over one gram of cocaine, 79 Xanax pills and two digital scales.
Tyler police say the amount of controlled substances and the digital scales were consistent with the defendant dealing narcotics.
During the punishment phase of the trial, the jury heard of Stewart's lengthy criminal history, as well as the fact the defendant absconded from his original trial date and had to been tracked down and re-arrested.
Smith County judicial records show Stewart had previously been arrested at least 15 times.
Based on his criminal history, the range of punishment was 15 years to life in prison.


Watch: New 'Iron Man suit' lets you hover in air!
An amateur inventor in the UK has built an Iron Man-like jet engine-powered exoskeleton suit that enables him to hover in the air like a superhero.
The futuristic ensemble consists of three sets of miniature jet engines attached to the arms and the back.
Richard Browning, a 38-year-old oil trader, had been secretly experimenting in his garage for 18 months, before he figured out the optimal number and position of the jet engines that allows him to fly with a minimal amount of equipment.
"The human body is very good at being trained to do specific things, and it's a useful structure, and the human mind is a pretty amazing machine," Browning said.
"So, we had this idea - rather than go and rely on aluminium structures to build the machine, rely on gyros and computers in order to achieve stability, why not rely on the human machine, keep it as raw and original as possible?" he said.
Piloting the device takes quite a lot of personal strength and body coordination, said Browning.
There is no steering mechanism, and speed and direction can be adjusted only by changing the direction of the engines' thrust, solely using upper-body strength.
"You have a trigger at your right hand, which controls the arm engines, and you have a trigger at your left hand, which controls the rear engines," Browning told the 'Live Science'.
The inventor added that he was inspired to create the suit by the Greek myth of Daedalus, who made himself wings to escape from captivity. The suit takes its name from the myth.
Currently, Browning can stay in the air for up to 10 minutes using the exosuit. He has kept his experiments at a running speed of about eight kilometres per hour and an altitude of only one to two metres above the ground.
Eventually a user could fly over 100 kilometres per hour and to an altitude of about 100 metres, Browning said.


High quality bread, rolls and pastries. We value good craftsmanship.
Bornholm's largest souvenirs- and gift shop. We always have great selection and fair prices.
1000 M2 with branded products at Outlet prices.
Mrs. Engel - handy clothing by goal. Come in and get inspiration for your new dress.
Spring 2019 - The most lovely shop with fashion for her and her home..
3 summer apartments on the west coast of Bornholm, in quiet surroundings.
Small shop where it is possible to buy appliances, vacuum cleaner bags, bulbs etc.
Bornholmske products. Specialities. Organic and Gluten. Coffee and Tea.
The island's largest selection of leather goods and travel accessories with trained personnel.
Supermarket with a large selection of the things you are missing. Meat, bread, wine, vegetables etc.
Shoes for every occasion.Vi leads many brands: ecco rieker Gabor green comfort Tamaris Clarks a.o.
A wide selection of clothes and bags for men and ladies.
We are a 600 m2 menswear shop with clothes for boys and men of all ages.
In Sommersted you will find beautiful fashion clothing, shoes, handbags, jewelry and accessories.
Cozy Habourbar in Gudhjem. Wineshop.
Hoddan has a wide range of scarves.


Wilma Hurskainen (b. 1979) lives and works in Helsinki.
Studied photography at Lahti Institute of Design and University of Art and Design / Aalto University in Helsinki. Works both as a freelance photographer for commissioned assignments and as an independent artist.
Wilma Hurskainen has had several solo exhibitions in Finland and the rest of Europe. She has participated in numerous group exhibitions throughout Europe and Asia, and her works have been exhibited at international art fairs and photography festivals. She was among the Fotofinlandia prize finalists in 2014 and 2016. Her works are included in collections of e.g. Helsinki Art Museum, Finnish Museum of Photography, Danish National Museum of Photography and Kiyosato Museum of Photographic Art.
She has published three monographs: Growth (2008, Musta taide), Heiress (2012, Kerber Verlag) and The Woman Who Married a Horse (2016, Kehrer Verlag). Her works are also included in Helsinki School books vol. III, IV and V (2009, 2011, 2014, Hatje Cantz) among many other books and magazines.