text:
\subsection{Equation \eqref{eq:theta_cond} implies that $g(x)$ is a descent direction}	\label{app:theta_descent}

\subsection{Derivation of \eqref{eq:GSG_bound1}}	\label{app:GSG_bound1}
\begin{align*}
	\| \nabla F(x) - \nabla \phi(x))\| &= \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \frac{1}{\sigma} f(x+\sigma u) u \right] - \nabla \phi(x)\right\| \\
	&= \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \frac{\phi(x+\sigma u) + \epsilon(x+\sigma u)}{\sigma} u \right] - \nabla \phi(x)\right\| \\
	&= \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \nabla \phi(x+\sigma u) - \nabla \phi(x) \right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \frac{\epsilon(x+\sigma u)}{\sigma} u \right]\right\| \\
	&\le \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \nabla \phi(x+\sigma u) - \nabla \phi(x) \right] \right\| + \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \frac{\epsilon(x+\sigma u)}{\sigma} u \right]\right\| \\
	&\le E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} [\|\nabla \phi(x+\sigma u) - \nabla \phi(x)\| ] + E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \left\| \frac{\epsilon(x+\sigma u)}{\sigma} u \right\| \right] \\
	&\leq L \sigma E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} [\| u \|] + \frac{\epsilon_f}{\sigma} E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} [\| u \|] \\
	&= \left( L \sigma + \frac{\epsilon_f}{\sigma} \right) \sqrt{2}\frac{\Gamma(\frac{n+1}{2})}{\Gamma(\frac{n}{2})} \leq \sqrt{n}L \sigma + \frac{\sqrt{n} \epsilon_f}{\sigma}.
\end{align*}

\subsection{Derivation of \eqref{eq:cGSG_bound1}}	\label{app:cGSG_bound1}
\begin{align*}
	& \| \nabla F(x) - \nabla \phi(x))\| \\
	&\qquad ={} \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \frac{\phi(x+\sigma u) + \epsilon(x+\sigma u) - \phi(x+\sigma u) - \epsilon(x+\sigma u)}{2\sigma} u \right] - \nabla \phi(x)\right\| \\
	&\qquad ={} \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[\frac{1}{2}\nabla \phi(x+\sigma u) + \frac{1}{2}\nabla \phi(x-\sigma u) - \nabla \phi(x)\right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \frac{\epsilon(x+\sigma u) - \epsilon(x+\sigma u)}{2\sigma} u \right] \right\| \\
	&\qquad\le{} \frac{1}{2}E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[\|\left(\nabla \phi(x+\sigma u) - \nabla \phi(x)\right) - (\nabla \phi(x) - \phi(x-\sigma u)) \| \right]\\
	&\qquad \qquad+ E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[\left\| \frac{\epsilon(x+\sigma u) - \epsilon(x+\sigma u)}{2\sigma} u \right\|\right] \\
	&\qquad \le{} \frac{1}{2}E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[\|\left(\nabla \phi(x+\sigma u) - \nabla \phi(x)\right) - (\nabla \phi(x) - \phi(x-\sigma u)) \| \right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \frac{\epsilon_f}{\sigma} \|u\| \right] \\
	&\qquad ={} \frac{1}{2}E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \|\left(\nabla^2 \phi(x+ \xi_1 u) - \nabla^2 \phi(x - \xi_2 u )\right) \sigma u \| \right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \frac{\epsilon_f}{\sigma} \|u\| \right],
\end{align*}
for some $0 \le \xi_1 \le \sigma$ and $0 \le \xi_2 \le \sigma$ by the intermediate value theorem. Then
\begin{align*}
	\| \nabla F(x) - \nabla \phi(x))\|
	\le{}& \frac{1}{2} E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[\| \nabla^2 \phi(x+ \xi_1 u) - \nabla^2 \phi(x - \xi_2 u ) \| \| \sigma u \| \right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \frac{\epsilon_f}{\sigma} \|u\| \right] \\
	\le{}& \frac{1}{2} E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[M \|\xi_1 u + \xi_2 u\| \cdot \sigma \|u\| \right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \frac{\epsilon_f}{\sigma} \|u\| \right] \\
	={}& \frac{1}{2} E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[|\xi_1 + \xi_2| \cdot \|u\|^2 M \sigma \right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \frac{\epsilon_f}{\sigma} \|u\| \right] \\
	\le{}& n M \sigma^2 + \frac{\sqrt{n} \epsilon_f}{\sigma} .
\end{align*}

\subsection{Derivation of \eqref{eq:mvn}}	\label{app:mvn}
For the first equality, let $A = \mathrm{E}_{u \sim \mathcal{N}(0,I)} (a^\intercal u)^2 u u ^\intercal$.
Then for any $(i,j) \in \{1,2,\dots, n\}^2$ with $i \neq j$, we have
\[ \begin{aligned}
    A_{ij} &= \mathrm{E} \left\{ (a^\intercal u )^2 u _i u _j \right\} \\
    &= \sum_{k=1}^n \sum_{l=1}^n \mathrm{E} \left\{ a_k u _k a_l u _l u _i u _j \right\} \\
    &= \sum_{k=i} \sum_{l=i} \mathrm{E} \left\{ a_k u _k a_l u _l u _i u _j \right\}
    + \sum_{k\neq i} \sum_{l=i} \mathrm{E} \left\{ a_k u _k a_l u _l u _i u _j \right\}
    + \sum_{k=i} \sum_{l\neq i} \mathrm{E} \left\{ a_k u _k a_l u _l u _i u _j \right\}
    + \sum_{k\neq i} \sum_{l\neq i}  \mathrm{E} \left\{ a_k u _k a_l u _l u _i u _j \right\} \\
    &= \mathrm{E} \left\{ a_i^2 u _i^3 u _j \right\}
    + \sum_{k\neq i} \mathrm{E} \left\{ a_k a_i u _k u _i^2 u _j \right\}
    + \sum_{l\neq i} \mathrm{E} \left\{a_i a_l u _l u _i^2 u _j \right\}
    + \mathrm{E} \left\{ u _i \right\} \sum_{k\neq i} \sum_{l\neq i}  \mathrm{E} \left\{ a_k u _k a_l u _l u _j \right\} \\
    &= 0 + \sum_{k\neq i} \mathrm{E} \left\{ a_k a_i u _k u _i^2 u _j \right\}
    + \sum_{l\neq i} \mathrm{E} \left\{a_i a_l u _l u _i^2 u _j \right\} + 0 \\
    &= \mathrm{E} \left\{ a_i a_j u _i^2 u _j^2 \right\} + \mathrm{E} \left\{ a_i a_j u _i^2 u _j^2 \right\} \\
    &= 2 a_i a_j.
\end{aligned} \]
For any $i \in \{1,2,\dots,n\}$,
\[ \begin{aligned}
    A_{ii} &= \mathrm{E} \left\{ (a^\intercal u )^2 u _i^2 \right\} \\
    &= \sum_{k=i} \sum_{l=i} \mathrm{E} \left\{ a_k u _k a_l u _l u _i^2 \right\}
    + \sum_{k\neq i} \sum_{l=i} \mathrm{E} \left\{ a_k u _k a_l u _l u _i^2 \right\}
    + \sum_{k=i} \sum_{l\neq i} \mathrm{E} \left\{ a_k u _k a_l u _l u _i^2 \right\}
    + \sum_{k\neq i} \sum_{l\neq i}  \mathrm{E} \left\{ a_k u _k a_l u _l u _i^2 \right\} \\
    &= \mathrm{E} \left\{ a_i^2 u _i^4 \right\}
    + \sum_{k\neq i} \mathrm{E} \left\{ a_k a_i u _k u _i^3 \right\}
    + \sum_{l\neq i} \mathrm{E} \left\{a_i a_l u _l u _i^3 \right\}
    + \mathrm{E} \left\{ u _i^2 \right\} \sum_{k\neq i} \sum_{l\neq i}  \mathrm{E} \left\{ a_k u _k a_l u _l \right\} \\
    &= 3a_i^2 + 0 + 0 + 1 \times \sum_{k=l\neq i} \mathrm{E} \left\{ a_k u _k a_l u _l \right\}
    = 3a_i^2 + \sum_{k\neq i} \mathrm{E} \left\{ a_k^2 u_k^2 \right\} \\
    &= 3a_i^2 + \sum_{k\neq i} a_k^2 = 2 a_i^2 + \sum_{k=1}^n a_k^2.
\end{aligned}\]
Then by writting the result in matrix format, we get $\mathrm{E}_{u \sim \mathcal{N}(0,I)} \left[ (a^\intercal u)^2 u u ^\intercal \right] = a^\intercal a I + 2 a a^\intercal$.

For the second equality, since the possibility density function of $\mathcal{N}(0, I)$ is even while $a^\intercal u \cdot \|u\|^k \cdot u u ^\intercal$ is an odd function, the expectation $E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{N}({0},I)} \left[a^T u \cdot \|u\|^k \cdot u u^T \right]$ is zero.

Because $E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{N}({0},I)} \left[\|u\|^k u^\intercal u \right] = E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{N}({0},I)} \left[\|u\|^{k+2} \right]$ is the $(k+2)$nd moment of a Chi distributed variable for all $k \in E}{\mbox{\boldmath$E$}{N}$, we have
\[ E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{N}({0},I)} \left[\|u\|^k u^\intercal u \right] = \frac{2^{1 + k/2} \Gamma((n+k+2)/2)}{\Gamma(n/2)}.
\]
This value is also the trace of the matrix $E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{N}({0},I)} \left[\|u\|^k u u^T \right]$.
Considering all $n$ elements on the diagonal of this matrix are the same, we have
\[
E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{N}({0},I)} \left[\|u\|^k u u^T \right]= \frac{2^{1 + k/2} \Gamma((n+k+2)/2)}{n \Gamma(n/2)} I \text{ for } k = 0,1, 2, \dots .
\]
For even $k$, this quantity is equal to $\prod_{i=1}^{k/2} (n + 2i)$.
For odd $k$, this quantity is equal to $\left[ \sqrt{2} \Gamma \left( \frac{n+1}{2} \right) \middle/ \Gamma \left( \frac{n}{2} \right) \right] \frac{1}{n} \prod_{i=1}^{(k+1)/2} (n + 2i - 1)$. Use the inequality $\sqrt{2} \left. \Gamma \left( \frac{n+1}{2} \right) \middle/ \Gamma \left( \frac{n}{2} \right) \right. \le \sqrt{n}$ for all $n \in E}{\mbox{\boldmath$E$}{N}$, we have
\[E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{N}({0},I)} \left[\|u\|^k u u^T \right]  \preceq (n+1)(n+3)\cdots(n+k) \cdot n^{-0.5} I \text{ for } k = 1, 3, 5, \dots .
\]

\subsection{Derivation of \eqref{eq:lower_req_eq1}}	\label{app:lb_1}

\begin{align*}
E}{\mbox{\boldmath$E$}{E} \left[\|g(x) - \nabla F(x)\|^2\right]
={}& E}{\mbox{\boldmath$E$}{E} \left[ \left \|\frac{1}{N} \sum_{i=1}^N \frac{f(x+\sigma u_i) - f(x)}{\sigma} u_i - \nabla F(x) \right\|^2 \right] \\
={}& \frac{1}{N} E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \left(\frac{f(x+\sigma u) - f(x)}{\sigma} \right)^2 u^\intercal u \right] - \frac{1}{N} \nabla F(x)^\intercal  \nabla F(x) \\
={}& \frac{1}{N} E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \left(a^\intercal u\right)^2 u^\intercal u \right] - \frac{1}{N} a^\intercal  a \\
={}& \frac{1}{N} (n + 1) a^\intercal a.
\end{align*}

\subsection{Derivation of \eqref{eq:lower_req_eq2}}	\label{app:lb_2}

The expression for $E\left[\|g(x) - \nabla F(x)\|^4\right]$ is a sum of $N^4$ terms with each term being the product of four vectors:
\[
E}{\mbox{\boldmath$E$}{E} \left[\|g(x) - \nabla F(x)\|^4\right] = \frac{1}{N^4} E}{\mbox{\boldmath$E$}{E} \left[ \sum_{i=1}^N \sum_{j=1}^N \sum_{k=1}^N \sum_{l=1}^N \prod_{w \in \{i,j,k,l\}} \left( \frac{f(x+\sigma u_w) - f(x)}{\sigma} u_w - \nabla F(x) \right) \right],
\]
where $\prod$ denotes the operation which is a product of the inner products of the two pairs of vectors. Specifically,  given  four vectors $a_1, a_2, a_3, a_4\in \mathbb{R}^n$, $\prod_{i \in \{1,2,3,4\}} a_i = (a_1^\intercal a_2) \cdot (a_3^\intercal a_4)$ and $\prod_{i \in \{1,1,2,2\}} a_i = (a_1^\intercal a_1) \cdot (a_2^\intercal a_2)$.

We first observe that $\prod_{w \in \{i,j,k,l\}} \left( \frac{f(x+\sigma u_w) - f(x)}{\sigma} u_w - \nabla F(x) \right)=0$
whenever one of the indices $(i,j,k,l)$ is different from all of the other ones. This is because all $u_w$,  for  $w \in \{i,j,k,l\}$ are independent of each other if their indices are different and
\[
E}{\mbox{\boldmath$E$}{E} \left[ \frac{f(x+\sigma u_w) - f(x)}{\sigma} u_w - \nabla F(x) \right] = 0.
\]

Thus we need only to consider the terms having one of the following conditions:
\begin{enumerate}
	\item $i=j=k=l$;
	\item $i=j \neq k=l$;
	\item $i=k \neq j=l$;
	\item $i=l \neq j=k$.
\end{enumerate}

First we consider the case: $i=j \neq k=l$, which occurs when $N>1$.
\[ \begin{aligned}
&E}{\mbox{\boldmath$E$}{E} \left[ \sum_{i=1}^N \sum_{k=1, k\neq i}^N \prod_{w \in \{i,i,k,k\}} \left( \frac{f(x+\sigma u_w) - f(x)}{\sigma} u_w - \nabla F(x) \right) \right] \\
&\qquad ={} \sum_{i=1}^N E}{\mbox{\boldmath$E$}{E} \left[ \left\| \frac{f(x+\sigma u_i) - f(x)}{\sigma} u_i - \nabla F(x) \right\|^2 \right] \cdot \sum_{k=1,k\neq i}^N E}{\mbox{\boldmath$E$}{E} \left[ \left\| \frac{f(x+\sigma u_k) - f(x)}{\sigma} u_k - \nabla F(x) \right\|^2 \right] \\
&\qquad ={} N(N-1) \left[ (n + 1) a^\intercal a \right]^2.
\end{aligned} \]

We now consider  two other cases: $i=k \neq j=l$ and $i=l \neq j=k$ that are essentially the same. We have
\[ \begin{aligned}
&E}{\mbox{\boldmath$E$}{E} \left[ \sum_{i=1}^N \sum_{k=1, k\neq i}^N \prod_{w \in \{i,k,i,k\}} \left( \frac{f(x+\sigma u_w) - f(x)}{\sigma} u_w - \nabla F(x) \right) \right] \\
&\qquad ={} \sum_{i=1}^N \sum_{k=1, k\neq i}^N E}{\mbox{\boldmath$E$}{E} \left\{ \left[ \left( \frac{f(x+\sigma u_i) - f(x)}{\sigma} u_i - \nabla F(x) \right)^\intercal \left( \frac{f(x+\sigma u_k) - f(x)}{\sigma} u_k - \nabla F(x) \right) \right]^2 \right\} \\
&\qquad ={} \sum_{i=1}^N \sum_{k=1, k\neq i}^N E}{\mbox{\boldmath$E$}{E} \left( \left\{ \left[ (a^\intercal u_i) u_i - a \right]^\intercal \left[ (a^\intercal u_k) u_k - a \right] \right\}^2 \right) \\
&\qquad ={} \sum_{i=1}^N \sum_{k=1, k\neq i}^N E}{\mbox{\boldmath$E$}{E} \left( \left[ (a^\intercal u_i) (a^\intercal u_k) (u_i^\intercal u_k)  - (a^\intercal u_i)^2 - (a^\intercal u_k)^2 + a^\intercal a \right]^2 \right) \\
&\qquad ={} \sum_{i=1}^N \sum_{k=1, k\neq i}^N E}{\mbox{\boldmath$E$}{E} \left[ \begin{array}{rl}
	&(a^\intercal u_i)^2 (a^\intercal u_k)^2 (u_i^\intercal u_k)^2 + (a^\intercal u_i)^4 + (a^\intercal u_k)^4 + (a^\intercal a)^2 \\
	+& 2 (a^\intercal a) (a^\intercal u_i) (a^\intercal u_k) (u_i^\intercal u_k) - 2(a^\intercal a) (a^\intercal u_i)^2 - 2(a^\intercal a) (a^\intercal u_k)^2 \\
	-& 2 (a^\intercal u_i)^3 (a^\intercal u_k) (u_i^\intercal u_k) - 2 (a^\intercal u_i) (a^\intercal u_k)^3 (u_i^\intercal u_k) + 2 (a^\intercal u_i)^2 (a^\intercal u_k)^2
\end{array} \right]  \\
&\qquad ={} \sum_{i=1}^N \sum_{k=1, k\neq i}^N \left[ \begin{array}{rl}
	& (n+8) (a^\intercal a)^2 + 3(a^\intercal a)^2 + 3(a^\intercal a)^2  + (a^\intercal a)^2 \\
	+& 2 (a^\intercal a)^2 - 2(a^\intercal a)^2 - 2(a^\intercal a)^2 \\
	-& 6 (a^\intercal a)^2 - 6 (a^\intercal a)^2 + 2 (a^\intercal a)^2
\end{array} \right] \\
&\qquad ={} \sum_{i=1}^N \sum_{k=1, k\neq i}^N (n+3) (a^\intercal a)^2 = N(N-1) (n+3) (a^\intercal a)^2
\end{aligned} \]

Finally, we have the $i=j=k=l$ case:
\[ \begin{aligned}
 &E}{\mbox{\boldmath$E$}{E} \left[ \sum_{i=1}^N \prod_{w \in \{i,i,i,i\}} \left( \frac{f(x+\sigma u_w) - f(x)}{\sigma} u_w - \nabla F(x) \right) \right] \\
&\qquad ={} N E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \left\| \frac{f(x+\sigma u) - f(x)}{\sigma} u - \nabla F(x) \right\|^4 \right] \\
&\qquad ={} N E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left\{ \left[ \left(\frac{f(x+\sigma u) - f(x)}{\sigma}\right)^2 u^\intercal u - 2 \left(\frac{f(x+\sigma u) - f(x)}{\sigma}\right) u^\intercal \nabla F(x) + \nabla F(x)^\intercal \nabla F(x) \right]^2 \right\} \\
&\qquad ={} N E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \begin{array}{rl}
&\left(\frac{f(x+\sigma u) - f(x)}{\sigma}\right)^4 (u^\intercal u)^2
+ 4 \left(\frac{f(x+\sigma u) - f(x)}{\sigma}\right)^2 \left( u^\intercal \nabla F(x) \right)^2 \\
+& \left( \nabla F(x)^\intercal \nabla F(x) \right)^2
- 4 \left(\frac{f(x+\sigma u) - f(x)}{\sigma}\right)^3  (u^\intercal u) \left( u^\intercal \nabla F(x) \right) \\
-& 4 \left(\frac{f(x+\sigma u) - f(x)}{\sigma}\right) (u^\intercal \nabla F(x)) (\nabla F(x)^\intercal \nabla F(x)) \\
+& 2 \left(\frac{f(x+\sigma u) - f(x)}{\sigma}\right)^2 (u^\intercal u) (\nabla F(x)^\intercal \nabla F(x))
\end{array} \right] \\
&\qquad ={} N E}{\mbox{\boldmath$E$}{E}_{u \sim \cN(0,I)} \left[ \begin{array}{rl}
&\left( a^\intercal u \right)^4 (u^\intercal u)^2
+ 4 \left( a^\intercal u \right)^2 \left( u^\intercal a \right)^2
+ \left( a^\intercal a \right)^2
- 4 \left( a^\intercal u \right)^3  (u^\intercal u) \left( u^\intercal a \right) \\
-& 4 \left( a^\intercal u \right) (u^\intercal a) (a^\intercal a)
+ 2 \left( a^\intercal u \right)^2 (u^\intercal u) (a^\intercal a)
\end{array} \right] \\
&\qquad ={} N \left[ \begin{array}{rl}
& 3 (n+4)(n+6) (a^\intercal a)^2 + 12 (a^\intercal a)^2 + (a^\intercal a)^2 - 12 (n+4) (a^\intercal a)^2 \\
-& 4(a^\intercal a)^2 + 2 (n+2) (a^\intercal a)^2
\end{array} \right] \\
&\qquad ={} N (3n^2 + 20n + 37) (a^\intercal a)^2
\end{aligned} \]
In summary, we have
\[
\begin{aligned}
&N^4 E}{\mbox{\boldmath$E$}{E} \left[ \|g(x) - \nabla F(x)\|^4 \right] \\
&\qquad ={} N(N-1) (n+1)^2 (a^\intercal a)^2 + 2N(N-1)(n+3) (a^\intercal a)^2 +N(3n^2 + 20n + 37) (a^\intercal a)^2 \\
&\qquad ={} N(N-1)(n^2 + 4n + 7) (a^\intercal a)^2 + N(3n^2 + 20n + 37) (a^\intercal a)^2.
\end{aligned}
\]

\subsection{Derivation of \eqref{eq:BSG_bound1}}	\label{app:BSG_bound1}

\begin{align*}
	\| \nabla F(x) - \nabla \phi(x))\| &= \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0,1))} \left[ \frac{n}{\sigma} f(x+\sigma u) u \right] - \nabla \phi(x)\right\| \\
	&= \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0,1))} \left[ \frac{n}{\sigma} (\phi(x+\sigma u) + \epsilon(x+\sigma u)) u \right] - \nabla \phi(x)\right\| \\
	&= \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{B}(0,1))} \left[ \nabla \phi(x+\sigma u) - \nabla \phi(x) \right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0,1))} \left[ \frac{n\epsilon(x+\sigma u)}{\sigma} u \right]\right\| \\
	&\le \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{B}(0,1))} \left[ \nabla \phi(x+\sigma u) - \nabla \phi(x) \right] \right\| + \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0,1))} \left[ \frac{n\epsilon(x+\sigma u)}{\sigma} u \right]\right\| \\
	&\le E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{B}(0,1))} [\|\nabla \phi(x+\sigma u) - \nabla \phi(x)\| ] + E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0,1))} \left[ \left\| \frac{n\epsilon(x+\sigma u)}{\sigma} u \right\| \right] \\
	&\leq L \sigma E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{B}(0,1))} [\| u \|] + \frac{n \epsilon_f}{\sigma} E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0,1))} [\| u \|] \\
	&= L \sigma \frac{n}{n+1} + \frac{n \epsilon_f}{\sigma} \leq L \sigma + \frac{n \epsilon_f}{\sigma}.
\end{align*}

\subsection{Derivation of \eqref{eq:cBSG_bound1}}	\label{app:cBSG_bound1}

\begin{align*}
	&  \| \nabla F(x) - \nabla \phi(x))\| \\
	&\qquad ={} \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0, 1))} \left[ \frac{n}{2\sigma} (\phi(x+\sigma u) + \epsilon(x+\sigma u) - \phi(x+\sigma u) - \epsilon(x+\sigma u)) u \right] - \nabla \phi(x)\right\| \\
	&\qquad ={} \left\| E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{B}(0, 1))} \left[\frac{1}{2}\nabla \phi(x+\sigma u) + \frac{1}{2}\nabla \phi(x-\sigma u) - \nabla \phi(x)\right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0, 1))} \left[ \frac{n}{2\sigma} (\epsilon(x+\sigma u) - \epsilon(x+\sigma u)) u \right] \right\| \\
	&\qquad \le{} \frac{1}{2}E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{B}(0, 1))} \left[\|\left(\nabla \phi(x+\sigma u) - \nabla \phi(x)\right) - (\nabla \phi(x) - \phi(x-\sigma u)) \| \right]\\
	&\qquad \qquad + E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0, 1))} \left[\left\| \frac{n}{2\sigma} (\epsilon(x+\sigma u) - \epsilon(x+\sigma u)) u \right\|\right] \\
	&\qquad \le{} \frac{1}{2}E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{B}(0, 1))} \left[\|\left(\nabla \phi(x+\sigma u) - \nabla \phi(x)\right) - (\nabla \phi(x) - \phi(x-\sigma u)) \| \right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0, 1))} \left[ \frac{n \epsilon_f}{\sigma} \|u\| \right] \\
	&\qquad ={} \frac{1}{2}E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{B}(0, 1))} \left[ \|\left(\nabla^2 \phi(x+ \xi_1 u) - \nabla^2 \phi(x - \xi_2 u )\right) \sigma u \| \right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0, 1))} \left[ \frac{n \epsilon_f}{\sigma} \|u\| \right],
\end{align*}
for some $0 \le \xi_1 \le \sigma$ and $0 \le \xi_2 \le \sigma$ by the intermediate value theorem. Then
\begin{align*}
	\| \nabla F(x) - \nabla \phi(x))\|
	\le{}& \frac{1}{2} E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{B}(0, 1))} \left[\| \nabla^2 \phi(x+ \xi_1 u) - \nabla^2 \phi(x - \xi_2 u ) \| \| \sigma u \| \right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0, 1))} \left[ \frac{n \epsilon_f}{\sigma} \|u\| \right] \\
	\le{}& \frac{1}{2} E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{B}(0, 1))} \left[M \|\xi_1 u + \xi_2 u\| \cdot \sigma \|u\| \right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0, 1))} \left[ \frac{n \epsilon_f}{\sigma} \|u\| \right] \\
	={}& \frac{1}{2} E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{B}(0, 1))} \left[|\xi_1 + \xi_2| \cdot \|u\|^2 M \sigma \right] + E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0, 1))} \left[ \frac{n \epsilon_f}{\sigma} \|u\| \right] \\
	\le{}& M \sigma^2 + \frac{n \epsilon_f}{\sigma} .
\end{align*}

\subsection{Derivation of \eqref{eq:uos}}	\label{app:uos}
The first and third equalities of \eqref{app:uos} comes from the first and third equalities of \eqref{eq:mvn}.
Considering any vector of iid Gaussian $v$, dividing by its own norm, can be expressed as $v = \|v\| u$. Moreover, $\|v\|$ and $u$ are independent. Thus any homogeneous polynomial $p$ in the entries of $u$ of degree $k$ has the property that
\[ E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0,1))} [ p(u) ] = \frac{E}{\mbox{\boldmath$E$}{E}_{v \sim \mathcal{N}(0,I)} [ p(v) ]}{E}{\mbox{\boldmath$E$}{E}_{v \sim \mathcal{N}(0,I)} \|v\|^k}.
\]
Then
\[ \begin{aligned}
E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0,1))} \left[(a^T u)^2 u u^T \right] &= \frac{E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{N}(0,I))} \left[(a^T u)^2 u u^T \right]}{E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{N}(0,I))} \| u \|^4} = \frac{a^T a I + 2 a a^T}{n(n+2)} \\
E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0,1))} \left[ \|u\|^k u u^T \right] &= \frac{E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{N}(0,I))} \left[ \|u\|^k u u^T \right]}{E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{N}(0,I))} \|u\|^{k+2}} = \frac{1}{n} I.
\end{aligned} \]

The second equality of \eqref{eq:uos} being 0 follows the same argument as that for the second equality of \eqref{eq:mvn}.

\subsubsection{Line Search Algorithms}

\subsubsection{Lower bound on $\delta$}
We have demonstrated that if $N\geq\Omega (\frac{3n}{\theta^2\delta})$, then  $E}{\mbox{\boldmath$E$}{P}(\|g(x) - \nabla \phi(x)\| \leq  \theta \|\nabla \phi(x)\|) \geq 1- \delta$; that is, having a  sufficiently large number of samples is {\em sufficient} to ensure accurate gradient approximations with a desired probability. A question that remains is how many samples are {\em necessary} to ensure that accurate gradient approximations are obtained with high probability. Here we derive a lower bound on the probability of failure for \eqref{eq:GSG} to satisfy condition \eqref{eq:theta_cond}; i.e.,
\begin{align} \label{eq:likelybad}
	E}{\mbox{\boldmath$E$}{P}\left(\|g(x) - \nabla \phi(x)\| > \theta \|\nabla \phi(x)\| \right).
\end{align}

We derive the lower bound for \eqref{eq:likelybad} theoretically, and then illustrate the lower bounds via numerical simulations for the specific case of a simple linear function of the form $f(x) =\phi(x)=a^\intercal x$,  where $a$ is an arbitrary nonzero vector in $\mathbb{R}^n$. For simplicity, through this subsection we assume that $\epsilon(x) = 0 $ for all $x \in E}{\mbox{\boldmath$E$}{R}^n$. In this case, for any $\sigma$, $\nabla F(x)=a$. Note also that in this case $\nabla f(x) = \nabla \phi(x) = \nabla F(x)=a$. We show that while theory gives us a weak lower bound, numerical simulations indicate that the lower bound is reasonably close to the upper bound, in terms of dependence on $n$.

We use the following lower bound on the tail of a random variable $X$, derived in \cite{petrov2007lower}. For any $b$ that satisfies $0 \le b \le E}{\mbox{\boldmath$E$}{E}\left[|X|\right] < \infty$,
\begin{align*}
	E}{\mbox{\boldmath$E$}{P}(|X| > b) \ge \frac{(E}{\mbox{\boldmath$E$}{E}[|X|] - b)^2}{E}{\mbox{\boldmath$E$}{E}[|X|^2]}.
\end{align*}

We apply this bound  to the random variable $\|g(x) - \nabla F(x)\|$,  and $b=\theta\|a\|$. We have
\begin{align*}
	E}{\mbox{\boldmath$E$}{P}\left(\|g(x) - \nabla \phi(x)\| > \theta \|\nabla \phi(x)\| \right) &= E}{\mbox{\boldmath$E$}{P}(\|g(x) - \nabla F(x)\| > b)\\
	  &= E}{\mbox{\boldmath$E$}{P}(\|g(x) - \nabla F(x)\|^2 > b^2) \\
	  &\ge \frac{\left(E}{\mbox{\boldmath$E$}{E}\left[\|g(x) - \nabla F(x)\|^2\right] - b^2 \right)^2}{E}{\mbox{\boldmath$E$}{E}\left[\|g(x) - \nabla F(x)\|^4\right]}
\end{align*}
for any $b$ such that $0 \le b \le \sqrt{E}{\mbox{\boldmath$E$}{E} \left[ \|g(x) - \nabla F(x)\|^2 \right]}$. The reason we consider the squared version of the condition is we are unable to calculate $E}{\mbox{\boldmath$E$}{E}\left[\|g(x) - \nabla F(x)\|^k\right]$ when $k$ is odd.

For brevity, we omit the derivations of $E}{\mbox{\boldmath$E$}{E}\left[\|g(x) - \nabla F(x)\|^2\right]$ and $E}{\mbox{\boldmath$E$}{E}\left[\|g(x) - \nabla F(x)\|^4\right]$ from the main paper, and refer the reader to Appendices  \ref{app:lb_1} and \ref{app:lb_2}, respectively. The required expressions are:
\begin{align}	\label{eq:lower_req_eq1}
	E}{\mbox{\boldmath$E$}{E} \left[\|g(x) - \nabla F(x)\|^2\right] &= \frac{1}{N} (n + 1) a^\intercal a, \\
	E}{\mbox{\boldmath$E$}{E} \left[ \|g(x) - \nabla F(x)\|^4 \right]
&= \frac{1}{N^3}\left((N-1)(n^2 + 4n + 7) (a^\intercal a)^2 + (3n^2 + 20n + 37) (a^\intercal a)^2\right). \label{eq:lower_req_eq2}
\end{align}
Thus for $\phi(x) = a^\intercal x$,
\begin{align*
E}{\mbox{\boldmath$E$}{P} \left( \|g(x) - a\| > \theta \|a\|\right) &\ge \frac{ N^4 \left( \frac{1}{N}(n+1) a^\intercal a - \theta^2 a^\intercal a \right)^2 }{N(N-1)(n^2 + 4n + 7) (a^\intercal a)^2 + N(3n^2 + 20n + 37) (a^\intercal a)^2} \\
&= \frac{ N \left( (n+1) a^\intercal a - N \theta^2 a^\intercal a  \right)^2 }{(N-1)(n^2 + 4n + 7) (a^\intercal a)^2 + (3n^2 + 20n + 37) (a^\intercal a)^2}\\
&= \frac{ N \left( (n+1)  - \theta^2 N \right)^2 }{(N-1)(n^2 + 4n + 7) + (3n^2 + 20n + 37) }
\end{align*}
for any $\theta$ and $N$ such that $0 \le \theta^2 a^\intercal a  \le \frac{1}{N} (n+1) a^\intercal a$.

Consider $n$ large enough such that  $4(n+1)^2 \ge n^2 + 4n +7$ which is satisfied for $n \ge \frac{\sqrt{13} -2}{3} \approx 0.54$; and $4(n+1)^2 \ge 3n^2 +20n+37$ which is satisfied for $n \ge 6 + \sqrt{69} \approx 14.31$ (henceforth we assume that $n \geq 15$). Then we have,
\begin{align*}
\frac{N((n+1) - \theta^2 N)^2}{(N-1)(n^2+4n+7) + (3n^2 +20n+37)} \ge
\frac{N((n+1) - \theta^2 N)^2}{(N-1)4(n+1)^2 + 4(n+1)^2} =
\frac{((n+1) - \theta^2 N)^2}{4(n+1)^2}.
\end{align*}
Thus, from
\begin{align*}
	E}{\mbox{\boldmath$E$}{P} \left( \|g(x) - a\| > \theta \|a\|\right) \ge \frac{((n+1) - \theta^2 N)^2}{4(n+1)^2} \ge \delta,
\end{align*}
we get
\begin{align*}
N \le \frac{(n+1)(1 - 2\sqrt{\delta})}{\theta^2}
\Rightarrow
E}{\mbox{\boldmath$E$}{P}(\|g(x) - \nabla \phi (x) \| > \theta \|\nabla \phi (x)\|) \ge \delta.
\end{align*}
It follows that for any $0 < \delta < \frac{1}{4}$, $n \ge 15$ and $N\leq \frac{1}{\theta^2}(1-2\sqrt{\delta})(n+1)$
\begin{align*}
E}{\mbox{\boldmath$E$}{P}(\|g(x) - \nabla \phi (x) \| > \theta \|\nabla \phi (x)\|) \ge \delta.
\end{align*}
In other words, to have $E}{\mbox{\boldmath$E$}{P}(\|g(x) - \nabla \phi (x) \| \le \theta \|\nabla \phi (x)\|) > 1 - \delta$, it is necessary to have
$N > \frac{(1 - 2\sqrt{\delta})}{\theta^2}(n+1)$, which is a linear function in $n$.

We now show through numerical simulation of the specific case of $\phi(x)=a^\intercal x$ that in fact for much larger values of $\delta$, $N\geq n$ is required
to achieve \eqref{eq:theta_cond} for any $\theta<1$. Specifically, Figure \ref{fig:lowerbound} shows the distribution of
\begin{align*}
   \theta=\frac{ \|g(x) - \nabla \phi(x)\| }{ \|\nabla \phi(x)\|},
\end{align*}
approximately computed via running $10000$ experiments,   where $\phi(x)=e^\intercal x$ ($e$ is a vector of all ones) and $n=32$, for different choices of $N \in \{ 1,2,4,8,16,32,64,128,256,512\}$. As is clear, $\theta$ is never smaller than $1$ when $N=1$. Moreover, $\theta$ is smaller than $\frac{1}{2}$, which is required by the theory in \cite{berahas2019global}, only about half the time when $N=128=4n$. Figure \ref{fig:lowerbound}(k) shows the percent of successful trials ($\theta < \frac{1}{2}$) versus the size of the sample set ($N$), and Table \ref{fig:lowerbound}(l) shows statistics of the empirical experiments for different  sizes of the sample set ($N$).
As expected, as $N$ grows, the value of $\theta$ decreases, something that is not surprising, but at the same time not captured by the derived lower bound. Thus, we conclude  that the theoretical  lower bound we derive here is weak and to satisfy  \eqref{eq:theta_cond} with $\theta<  \frac{1}{2}$ and  probability of at least $\frac{1}{2}$ the size of the sample set needs to be larger than $n$.  A stronger theoretical lower bound supporting this claim remains an open question.

 In Section  \ref{sec:num} we present numerical evidence that shows that for a variety of functions choosing $N$ to be a small constant almost always results in  large values of $ \frac{ \|g(x) - \nabla \phi(x)\| }{ \|\nabla \phi(x)\|}
 $ with probability close to $1$.

\begin{figure}[ht]
    \centering
    \begin{subfigure}{.19\textwidth}
        \centering
        \includegraphics[trim=10 5 60 25,clip,width=0.95\linewidth]{figs/LowerBnd/lower_1}
        \caption{  $N=1 \; (n/32)$}
    \end{subfigure}
    \begin{subfigure}{.19\textwidth}
        \centering
        \includegraphics[trim=10 5 40 25,clip,width=0.95\linewidth]{figs/LowerBnd/lower_2}
        \caption{  $N=2 \; (n/16)$}
    \end{subfigure}
    \begin{subfigure}{.19\textwidth}
        \centering
        \includegraphics[trim=10 5 40 25,clip,width=0.95\linewidth]{figs/LowerBnd/lower_4}
        \caption{  $N=4 \; (n/8)$}
    \end{subfigure}
    \begin{subfigure}{.19\textwidth}
        \centering
        \includegraphics[trim=10 5 40 25,clip,width=0.95\linewidth]{figs/LowerBnd/lower_8}
        \caption{  $N=8 \; (n/4)$}
    \end{subfigure}
    \begin{subfigure}{.19\textwidth}
        \centering
        \includegraphics[trim=10 5 40 25,clip,width=0.95\linewidth]{figs/LowerBnd/lower_16}
        \caption{  $N=16 \; (n/2)$}
    \end{subfigure}

    \vspace{0.25cm}
     \begin{subfigure}{.19\textwidth}
        \centering
        \includegraphics[trim=10 5 40 25,clip,width=0.95\linewidth]{figs/LowerBnd/lower_32}
        \caption{  $N=32 \; (n)$}
    \end{subfigure}
    \begin{subfigure}{.19\textwidth}
        \centering
        \includegraphics[trim=10 5 40 25,clip,width=0.95\linewidth]{figs/LowerBnd/lower_64}
        \caption{  $N=64 \; (2n)$}
    \end{subfigure}
    \begin{subfigure}{.19\textwidth}
        \centering
        \includegraphics[trim=10 5 40 25,clip,width=0.95\linewidth]{figs/LowerBnd/lower_128}
        \caption{  $N=128 \; (4n)$}
    \end{subfigure}
    \begin{subfigure}{.19\textwidth}
        \centering
        \includegraphics[trim=10 5 40 25,clip,width=0.95\linewidth]{figs/LowerBnd/lower_256}
        \caption{  $N=256 \; (8n)$}
    \end{subfigure}
    \begin{subfigure}{.19\textwidth}
        \centering
        \includegraphics[trim=10 5 40 25,clip,width=0.95\linewidth]{figs/LowerBnd/lower_512}
        \caption{  $N=512 \; (16n)$}
    \end{subfigure}

     \vspace{0.25cm}
    \begin{subfigure}{.35\textwidth}
        \centering
        \includegraphics[trim=20 5 40 25,clip,width=0.95\linewidth]{figs/LowerBnd/lower_all}
        \caption{  Percent of successful trials vs. $N$}
    \end{subfigure}
    \begin{subfigure}{.51\textwidth}
    \scriptsize
        \centering
\begin{tabular}{ccccc}
\toprule
$\pmb{N}$   & \textbf{Mean ($\pmb{\theta}$)} & \textbf{Median ($\pmb{\theta}$)} & \textbf{Variance ($\pmb{\theta}$)} & \begin{tabular}[c]{@{}c@{}}\textbf{Percent of} \\ \textbf{Successful} \\ \textbf{Trials}\end{tabular} \\ \midrule
1 ($n/32$)  & 4.62            & 3.69              & 11.44               & 0                                                                          \\ \hdashline
2  ($n/16$) & 3.62            & 3.23              & 3.67                & 0                                                                          \\ \hdashline
4   ($n/8$) & 2.70            & 2.53              & 1.07                & 0                                                                          \\ \hdashline
8   ($n/4$) & 1.96            & 1.87              & 0.31                & 0                                                                          \\ \hdashline
16  ($n/2$) & 1.41            & 1.36              & 0.093               & 0                                                                          \\ \hdashline
32  ($n$) & 1.00            & 0.98              & 0.032               & 0                                                                          \\ \hdashline
64 ($2n$) & 0.71            & 0.70              & 0.012               & 1.04                                                                       \\ \hdashline
128 ($4n$) & 0.50            & 0.50              & 0.0051              & 49.53                                                                      \\ \hdashline
256 ($8n$) & 0.36            & 0.35              & 0.0023              & 99.56                                                                      \\ \hdashline
512 ($16n$) & 0.25            & 0.25              & 0.0011              & 100                                                                  \\      \bottomrule
\end{tabular}
  \caption{ Summary of Results}
    \end{subfigure}

    \caption{Distribution of $\theta$ for $\phi(x)=e^\intercal x$, at $x=e$, where $e$ is a vector of all ones, and  $n=32$.  }
    \label{fig:lowerbound}
\end{figure}

\section{Introduction}

\input{intro2.tex}

\section{Gradient Approximations and Sampling}	\label{sec:grad_approx}

\input{sampling_mod_grad_smooth.tex}

\section{Numerical Results}\label{sec:num}

\input{num_res.tex}

\pagebreak

\section{Final Remarks} \label{sec:finrem}
\input{finalremarks.tex}

\bibliographystyle{plain}

\subsection{Assumptions}

Throughout the paper we will assume that the noise in the function evaluations $\epsilon(x)$ is bounded for all $x \in E}{\mbox{\boldmath$E$}{R}^n$, and that $\phi$ is Lipschitz smooth.
\begin{assumption}	\label{assum:bounded_noise}
\textbf{(Boundedness of Noise in the Function)} There is a constant $\epsilon_f \geq 0$ such that $| f(x) - \phi(x)| = |\epsilon(x)| \leq \epsilon_f$ for all $x \in E}{\mbox{\boldmath$E$}{R}^n$.
\end{assumption}
\begin{assumption}	\label{assum:lip_cont}
\textbf{(Lipschitz continuity of the gradients of $\pmb{\phi}$)}
The function $\phi$ is continuously differentiable, and the gradient of $\phi$ is $L$-Lipschitz continuous for all $x \in E}{\mbox{\boldmath$E$}{R}^n$.
\end{assumption}

In some cases, to establish better approximations of the gradient, we will  assume that  $\phi$ has  Lipschitz continuous Hessians.
\begin{assumption}	\label{assum:lip_cont_hess}
\textbf{(Lipschitz continuity of the Hessian of $\pmb{\phi}$)}
The function $\phi$ is twice continuously differentiable, and the Hessian of $\phi$ is $M$-Lipschitz continuous for all $x \in E}{\mbox{\boldmath$E$}{R}^n$.
\end{assumption}

\subsection{Summary of Results}
We begin by stating a condition that is often used in the analysis of first order methods with inexact gradient computations:
\begin{align}	\label{eq:theta_cond}
	\| g(x) - \nabla \phi(x) \| \leq \theta \|  \nabla \phi(x) \|,
\end{align}
for some $\theta \in [0,1)$. This condition is referred to as the \emph{norm condition} and was introduced and studied in \cite{carter1991global} in the context of trust-region methods with inexact gradients. Note, this condition implies that $g(x)$ is a descent direction for the function $\phi$. In \cite{berahas2019global} the authors establish expected complexity bounds for a generic line search algorithm that uses gradient approximations in lieu of the true gradient, under the condition that the gradient estimate $g(x)$ satisfies \eqref{eq:theta_cond} for sufficiently small $\theta$ and with sufficiently high probability.

Clearly, unless we know $\|  \nabla \phi(x) \|$, condition \eqref{eq:theta_cond} may be hard or impossible to verify or guarantee. There is significant amount of work that attempts to circumvent this difficulty; see e.g., \cite{byrd2012sample,cartis2018global,paquette2018stochastic}. In \cite{byrd2012sample} a practical approach to estimate $\|  \nabla \phi(x_k) \|$ is proposed  and  used to ensure some approximation of \eqref{eq:theta_cond} holds. In \cite{cartis2018global,paquette2018stochastic} the condition \eqref{eq:theta_cond} is replaced by
\begin{align*}
	\| g(x) - \nabla \phi(x) \| \leq \kappa \alpha_k   \|  g(x) \|,
\end{align*}
for some $\kappa > 0 $, and convergence rate analyses are derived for a line search method that has access to deterministic function values in \cite{cartis2018global} and stochastic function values (with additional assumptions) in \cite{paquette2018stochastic}. However, for the methods studied in this paper, condition \eqref{eq:theta_cond} turns out to be achievable. Therefore, in this paper, we establish conditions under which  \eqref{eq:theta_cond}
 holds either deterministically or with sufficiently high probability. Given a point $x$, all of these methods compute $g(x)$  using either \eqref{eq:GSG_intro} or \eqref{eq:cGSG_intro}, where the $u_i$'s are the \emph{sampling directions} and $\sigma$ is the \emph{sampling radius}. The methods vary in their selection of the \emph{size of the sample set} $N$, the set  $\{u_i: i=1, \ldots, N\}$ and the corresponding set $\{\tilde u_i: i=1, \ldots, N\}$, and the \emph{sampling radius} $\sigma$.

 Here, upfront, we present a simplified summary of the conditions on $N$, $\sigma$ and $\nabla \phi(x)$ for each method that we consider in this paper to guarantee condition \eqref{eq:theta_cond}; see Table \ref{tbl:bounds1}. For more detailed results  see Section \ref{sec:summary}, Tables \ref{tbl:bounds_full} and \ref{tbl:bounds_full2}. Note that for the smoothing methods the condition \eqref{eq:theta_cond} holds with probability $1-\delta$ and the number of samples depends on $\delta$. Moreover, the bounds on $N$ for the smoothing methods are a simplification of the more detailed bounds derived in the paper and apply when $n\geq4$, while for smaller $n$ some of the constants are larger. We should note that the constants in the bound on $N$ are somewhat smaller for larger $n$.

 \begin{table}[h!]

\caption{ Simplified conditions under assumption that $n\geq4$. Bounds on $N$, $\sigma$ and $\nabla \phi(x)$ that ensure $\| g(x) - \nabla \phi(x) \| \leq \theta\|\nabla \phi(x)\|$ ($\pmb{^*}$ denotes result is with probability $1-\delta$).}
\small
\label{tbl:bounds1}
\centering
\begin{tabular}{lccc}
\toprule
\begin{tabular}[l]{@{}l@{}}\textbf{Gradient} \\  \textbf{Approximation}\end{tabular} &
 \textbf{$\pmb{N}$} &
 \textbf{$\pmb{\sigma}$} &  \textbf{$\pmb{\| \nabla \phi(x) \|}$} \\  \midrule

\begin{tabular}[l]{@{}l@{}}\textbf{Forward Finite} \\  \textbf{Differences}\end{tabular} & $n$ & $\left[2 \sqrt{\frac{\epsilon_f}{L}},\frac{\theta \| \nabla \phi(x)\| }{\sqrt{n}L} \right]$ & $\frac{2\sqrt{nL\epsilon_f}}{\theta}$ \\ \hdashline
 \begin{tabular}[l]{@{}l@{}}\textbf{Central Finite} \\  \textbf{Differences}\end{tabular} & $n$ & $ \left[ \sqrt[3]{\frac{6\epsilon_f}{M}}, \sqrt{\frac{3 \theta \| \nabla \phi(x)\|}{\sqrt{n}M}} \right]$ & $\frac{2 \sqrt{n} \sqrt[3]{M \epsilon_f^2}}{\sqrt[3]{6} \theta}$  \\ \hdashline
 \begin{tabular}[l]{@{}l@{}}\textbf{Linear} \\  \textbf{Interpolation}\end{tabular} & $n$ & $\left[2 \sqrt{\frac{\epsilon_f}{L}},\frac{\theta \| \nabla \phi(x)\| }{\| Q_\mathcal{X}^{-1}\|\sqrt{n}L} \right]$ & $\frac{2\| Q_\mathcal{X}^{-1}\|\sqrt{nL\epsilon_f}}{\theta}$ \\ \hdashline
 \begin{tabular}[l]{@{}l@{}}\textbf{Gaussian Smoothed} \\  \textbf{Gradients}$\pmb{^*}$\end{tabular} & $\frac{12n }{\delta  \theta^2 } + \frac{(n+20)}{16\delta }  $ & $\left[ \sqrt{\frac{\epsilon_f}{L}},\frac{ \theta\| \nabla \phi(x)\|}{6nL } \right]$ & $\frac{6n\sqrt{L\epsilon_f}}{\theta}$ \\ \hdashline
 \begin{tabular}[l]{@{}l@{}}\textbf{Centered Gaussian} \\  \textbf{Smoothed Gradients}$\pmb{^*}$\end{tabular} & $\frac{12n  }{\delta  \theta^2 } +
	 \frac{(n+30)}{144\delta  }  $ & $\left[ \sqrt[3]{\frac{\epsilon_f}{\sqrt{n}M}}, \sqrt{\frac{\theta\| \nabla \phi(x)\|}{12n^{3/2}M }} \right]$ & $\frac{12\sqrt[3]{n^{7/2}M\epsilon_f^2}}{\theta}$ \\ \hdashline
	  \begin{tabular}[l]{@{}l@{}}\textbf{Sphere Smoothed} \\  \textbf{Gradients}$\pmb{^*}$\end{tabular} & $ \left[\frac{8n }{\theta^2 } + \frac{8n}{3 \theta} + \frac{(11n +104)}{24}  \right] \log \frac{n+1}{\delta}$ & $\left[ \sqrt{\frac{n\epsilon_f}{L}},\frac{ \theta\| \nabla \phi(x)\|}{4\sqrt{n}L } \right]$ & $\frac{4n\sqrt{L\epsilon_f}}{\theta}$ \\ \hdashline
 \begin{tabular}[l]{@{}l@{}}\textbf{Centered Sphere} \\  \textbf{Smoothed Gradients}$\pmb{^*}$\end{tabular} & $ \left[\frac{8n }{\theta^2 } +  \frac{8n}{3 \theta} + \frac{(9n + 192)}{27} \right] \log \frac{n+1}{\delta}$ & $\left[ \sqrt[3]{\frac{n\epsilon_f}{M}}, \sqrt{\frac{\theta\| \nabla \phi(x)\|}{4\sqrt{n}M }} \right]$ & $\frac{4\sqrt[3]{n^{7/2}M\epsilon_f^2}}{\theta}$ \\

 \bottomrule
\end{tabular}

 \end{table}
From Table \ref{tbl:bounds1} we note that the bounds on $N$ for all methods have the same dependence (order of magnitude) on the dimension $n$; however, for the smoothing methods the constants in the bound are significantly larger than those for deterministic methods, such as finite differences. This suggests that deterministic methods may be more efficient, at least in the setting considered in this paper, when accurate gradient estimates are  desired. The bounds on the sampling radius are comparable for the smoothing and deterministic methods, as we will discuss in detail later in the paper. Our numerical results support our theoretical observations.

\subsubsection{Linear Models}

Let us consider the following sample set  $\mathcal{X}=\{x+\sigma u_1, x+\sigma u_2, \ldots, x+\sigma u_n\}$ for some $\sigma >0$. In other words, we have $n$ directions denoted by $u_i \in E}{\mbox{\boldmath$E$}{R}^n$ and we sample $f$ along those directions, around $x$, using a sampling radius of size $\sigma$. We assume $f(x)$ is known (function value at $x$).  Let $F_\mathcal{X} \in E}{\mbox{\boldmath$E$}{R}^n$ be a vector whose entries are
$f(x+\sigma u_i) - f(x)$, for $i=1\dots n$, and let $Q_\mathcal{X} \in E}{\mbox{\boldmath$E$}{R}^{n \times n}$ define a matrix whose rows are given by $u_i$ for $i=1\dots n$. The model in \eqref{eq:lin_mod} is constructed to satisfy  the interpolation conditions,
\begin{align*}
	f(x+\sigma u_i)=m(x+\sigma u_i), \quad \forall i=1, \ldots, n,\\
\end{align*}
which can be written as
\begin{align} \label{eq:main_system}
	\sigma Q_\mathcal{X} g=F_\mathcal{X}.
\end{align}

If the matrix $Q_\mathcal{X}$ is nonsingular, then $m(y) = f(x) + g(x)^\intercal (y-x)$, with $g(x) = \frac{1}{\sigma}Q_\mathcal{X}^{-1}F_\mathcal{X}$, is a linear interpolation model of $f(y)$ on the sample set $\mathcal{X}$. When $Q_\mathcal{X}$ is the identity matrix, then we recover standard forward finite difference gradient estimation. In the specific case when $Q_\mathcal{X}$ is
orthonormal, then $Q_\mathcal{X}^{-1} = Q_\mathcal{X}^\intercal$, thus $g(x)$ is written as
\begin{align*}
	g(x) = \sum_{i=1}^n \frac{f(x+\sigma u_i) - f(x)}{\sigma}u_i.
\end{align*}

Next we derive a bound on $\|g(x)-\nabla \phi(x)\|$. This result is an extension of the results presented in \cite{ConnScheVice08c,conn2008geometry} to account of the noise in the function evaluations.

\begin{theorem} \label{thm:bnd_linmod}Suppose that Assumptions \ref{assum:bounded_noise} and \ref{assum:lip_cont} hold. Let $\mathcal{X}=\{x+\sigma u_1,\dots,x+\sigma u_n \}$ be a set of interpolation points such that $\max_{1\leq i \leq n}\|u_i\|\leq 1$  and
$Q_\mathcal{X}$ be nonsingular. Then, for all $x \in E}{\mbox{\boldmath$E$}{R}^n$,
\begin{align*}
	\|g({x}) - \nabla \phi({x})\| \leq \frac{\| Q_\mathcal{X}^{-1}\|_2\sqrt{n}L \sigma }{2} + \frac{2 \| Q_\mathcal{X}^{-1}\|_2\sqrt{n} \epsilon_f}{\sigma}.
\end{align*}
\end{theorem}

\begin{proof}
From the interpolation conditions and the mean value theorem, $\forall i=1, \ldots, n$ we have
\begin{align*}
\sigma g(x)^\intercal u_i &=f(x+\sigma u_i)-f(x)=\phi(x+\sigma u_i)-\phi(x)+\epsilon(x+\sigma u_i)-\epsilon(x)\\
&=\int_{0}^1 \sigma u_i^\intercal\nabla \phi(x+t\sigma u_i)dt+\epsilon(x+\sigma u_i)-\epsilon(x).
\end{align*}
From the $L$-smoothness of $\phi(\cdot)$ and the bound on $\epsilon(\cdot)$ we have
\begin{align*}
\sigma |(g(x)-\nabla \phi(x))^\intercal u_i| \leq  \frac {L\sigma^2 \|u_i\|^2}{2}+2\epsilon_f, \quad \forall i=1, \ldots, n
\end{align*}
which in turn implies
\begin{align*}
 \| Q_{\cal X}(g(x)-\nabla \phi(x))\| \leq  \frac {\sqrt{n}L\sigma  }{2}+\frac{2 \sqrt{n} \epsilon_f}{\sigma},
\end{align*}
and the theorem statement follows.
\end{proof}

This result has the implication that large $\| Q_\mathcal{X}^{-1}\|$ can cause large deviation of $g(x)$ from $\nabla \phi(x)$. Thus, it is  desirable to select $\mathcal{X}$ in such a way that the condition number of $Q_\mathcal{X}^{-1}$ is small, which is clearly optimized when $Q_\mathcal{X}$ is orthonormal. Thus, we trivially recover the theorem for FFD, and moreover, extend this result to any orthonormal set of directions $\{u_1, u_2 \ldots, u_n\}$, such as those used in \cite{choro2}.

Aside from the condition number, the  important difference between general interpolation sets and orthonormal ones is in the computational cost of evaluating $g(x)$. In particular, $g(x)$ is obtained by solving a system of linear equations given by \eqref{eq:main_system},
which in general requires ${\cal O}(n^3)$ computations, but that reduces to ${\cal O}(n^2)$ in the case of general orthornormal matrices $Q_\mathcal{X}$, and further reduces to ${\cal O}(n)$ for $Q_\mathcal{X}=I$, as in the case of FFD.
In  \cite{choro2}, it is proposed to use  scaled randomized Haddamard matrices as $Q_\mathcal{X}$. This is only possible if the problem dimension is a power of $2$, but it reduces linear algebra cost  of matrix-vector products
from  ${\cal O}(n^2)$ to  ${\cal O}(n\log n)$.

On the other hand, using general sample sets allows for greater flexibility (within an optimization algorithm), in particular enabling the re-use of sample points from prior iterations. When using FFD to compute $g(x)$, $n$ function evaluations are always required, while when using interpolation it is possible to update the interpolation set by replacing only one (or a few) sample point(s) in the set $\mathcal{X}$. It is important to note that while $\mathcal{X}$ can be fairly general, the condition number of  the matrix $Q_\mathcal{X}$ has to remain bounded for Theorem \ref{thm:bnd_linmod} to be useful. The sets with bounded condition number of  $Q_\mathcal{X}$ are called {\em well-poised}; see  \cite{ConnScheVice08c} for  details about the construction and maintenance of interpolation sets in model based trust region DFO methods.

The bounds of Theorem \ref{thm:bnd_linmod} are similar to those of Theorem \ref{thm:FFDbound}, hence, if the sampling radius $\sigma$ is chosen to satisfy
 \begin{align*}
	2\sqrt{ \frac{\epsilon_f}{L}}\leq \sigma \leq \frac{\theta\|\nabla \phi(x)\|}{\| Q_\mathcal{X}^{-1}\| \sqrt{n}L}, \qquad \text{with} \qquad \|\nabla \phi(x)\|\geq\frac{2 \| Q_\mathcal{X}^{-1}\|\sqrt{nL\epsilon_f}}{\theta},
 \end{align*}
 then \eqref{eq:theta_cond} holds.
 Since the condition number of  $\|Q_\mathcal{X}^{-1} \|$ may not be known when $\sigma$ is chosen, an upper bound on  $\|Q_\mathcal{X}^{-1} \|$, which needs to be imposed for convergence, can used instead;
 see  \cite{ConnScheVice08c}.

 It is possible to derive an analogue of Theorem \ref{thm:CFDbound} by including $n$ additional sample points  $\{x-\sigma u_1,\dots,x-\sigma u_n \}$ in the gradient estimation procedure. Namely, two sample sets are used,  $\mathcal{X}^+=\{x+\sigma u_1, x+\sigma u_2, \ldots x+\sigma u_n\}$ and $\mathcal{X}^-=\{x-\sigma u_1, x-\sigma u_2, \ldots x-\sigma u_n\}$, with corresponding matrices $Q_{\mathcal{X}^+}$
and $Q_{\mathcal{X}^-}$. The linear model $m(y)=f(x)+g^\intercal(y-x)$ is then computed as an average of the two interpolation models, that is
\begin{align*}
	 g=\frac{g_0^+ + g_0^-}{2}= \frac{1}{2\sigma}[Q_{\mathcal{X}^+}^{-1}F_{\mathcal{X}^+}+Q_{\mathcal{X}^-}^{-1}F_{\mathcal{X}^-}].
\end{align*}
The gradient estimates are computed in this way in \cite{choro}, for the case of orthonormal sets and symmetric finite difference computations. Similarly to the CFD, this results in better accuracy bounds in terms of $\sigma$; however, this requires additional $n$ function evaluations at each iteration, which contradicts the original idea of using interpolation as a means for reducing the per-iteration function evaluation cost.

\subsection{Gradient Approximation Accuracy} \label{sec:num_grad_approx}
\input{num_grad_approx.tex}

\subsection{Performance of Line Search DFO Algorithm with Different Gradient Approximations} \label{sec:alg_perf}
\input{num_alg_perf.tex}

\paragraph{Reinforcement Learning Tasks \cite{brockman2016openai}}
\input{RL.tex}

\subsection{Gradient Estimation via Standard Finite Differences}	\label{sec:fd}

\input{fd_approx.tex}

\subsection{Gradient Estimation via Linear Interpolation}	\label{sec:lin_mod}

\input{lin_interp.tex}

\subsection{Gradient Estimation via Gaussian Smoothing} \label{sec:gauss_smooth}

\input{gaussian_smoothed.tex}

\subsection{Gradient Estimation via Smoothing on a Sphere} \label{sec:ball_smooth}

\input{sphere_smoothed.tex}

\subsection{Smoothing vs. Interpolation gradients}
\input{smoothing_vs_interp}

\subsection{Summary of Results}\label{sec:summary}
\input{summary_of_results}
\subsubsection{Linear Models}
The GSG estimate, on the other hand is written as,
  \begin{align*}
	g_{GSG}= \frac{1}{n}Q_\mathcal{X}^TF_\mathcal{X}/\sigma=\frac{1}{n}Q_\mathcal{X}^T Q_\mathcal{X}g_{LI}.
\end{align*}
Hence, we obtain
  \begin{align*}
\|g_{LI}-g_{GSG}\|= \left\|\left(I-\frac{1}{n}Q_\mathcal{X}^TQ_\mathcal{X}\right)g_{LI}\right\|.
\end{align*}
We know that, when $\epsilon(x) = 0$ for all $x \in E}{\mbox{\boldmath$E$}{R}^n$, the difference $\|g_{LI}-\nabla \phi(x)\|$ goes to zero as $\sigma\to 0$. However, $\|(I-\frac{1}{n}Q_\mathcal{X}^TQ_\mathcal{X})g_{LI}\|$ does not, as it does not depend on $\sigma$. While we have $E}{\mbox{\boldmath$E$}{E}[\frac{1}{n}Q_\mathcal{X}^TQ_\mathcal{X}]=I$, nevertheless, with non-negligible probability, the matrix
$\|(I-\frac{1}{n}Q_\mathcal{X}^TQ_\mathcal{X})g_{LI}\|\geq \nu \|g_{LI}\|$ for some fixed non-negligible value of $\lambda$, for example, $\nu>1/2$.

The intuition for the BSG can be derived in the same manner.

\subsubsection{Line Search Algorithms}
Bernstein's inequality applies here because, unlike GSG (and cGSG), BSG (and cBSG) enjoys a deterministic bound on the error term $n \frac{f(x+\sigma {u}) - f(x)}{\sigma} {u}  - F(x)$; see proof of Lemma \ref{lem:prob_bnd_sphere_smoothed_bern}.

\begin{lemma} 	\label{lem:prob_bnd_sphere_smoothed_bern}
Let $F$ be a ball smoothed approximation of $f$ \eqref{eq:Fball}. Under Assumption  \ref{assum:lip_cont}, if $g(x)$ is  calculated via \eqref{eq:BSG} with sample size
\begin{align*}
	N \ge \left[ \frac{2n^2}{r^2} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{L^2\sigma^2}{4} + \frac{4\epsilon_f^2}{\sigma^2} + 2 L \epsilon_f  \right)  + \frac{2n}{3r} \left( 2 \|\nabla f(x)\| + L \sigma + \frac{4\epsilon_f}{\sigma} \right) \right] \log \frac{n+1}{\delta},
\end{align*}
then, for all $x \in E}{\mbox{\boldmath$E$}{R}^n$, $\|g(x) - \nabla F(x)\| \le r$ holds with probability at least $1 - \delta$, for any $r>0$ and $0< \delta <1$.

Alternatively, under Assumption  \ref{assum:lip_cont_hess} if $g(x)$ is calculated via \eqref{eq:cBSG} with sample size $2N$ where
\begin{align*}
	N \ge \left[ \frac{2n^2}{r^2} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{M^2\sigma^4}{36} + \frac{\epsilon_f^2}{\sigma^2} + \frac{M\sigma \epsilon_f}{3} \right)  + \frac{2n}{3r} \left( 2 \|\nabla \phi(x)\| + \frac{M \sigma^2}{3} + \frac{2 \epsilon_f}{\sigma} \right) \right] \log \frac{n+1}{\delta},
\end{align*}
then, for all $x \in E}{\mbox{\boldmath$E$}{R}^n$, $\|g(x) - \nabla F(x)\| \le r$ holds with probability at least $1 - \delta$, for any $r>0$ and $0< \delta <1$.
\end{lemma}

\begin{proof}
We first note that
\begin{align*}
E}{\mbox{\boldmath$E$}{E}_{u \sim \mathcal{U}(\mathcal{S}(0,1))} \left[\frac{n}{N} \frac{f(x+\sigma u) - f(x)}{\sigma} u - \frac{1}{N} \nabla F(x)\right] &= 0,
\end{align*}
and
\begin{align*}
&\left\| \frac{n}{N} \frac{f(x+\sigma {u}) - f(x)}{\sigma} {u}  - \frac{1}{N} \nabla F(x) \right\| \\
&\qquad \le{}  \frac{n}{N\sigma} \left| f(x+\sigma u) - f(x)\right|  \|u\| + \frac{n}{N\sigma} E}{\mbox{\boldmath$E$}{E}_{v \sim \mathcal{U}(\mathcal{S}(0,1))}\left[ \left| f(x+\sigma v) - f(x) \right| \|v\| \right]\\
&\qquad ={} \frac{n}{N\sigma} \left| \phi(x+\sigma u) + \epsilon(x+\sigma u) - \phi(x) - \epsilon(x) \right| \\
&\qquad \quad +  \frac{n}{N\sigma} E}{\mbox{\boldmath$E$}{E}_{v \sim \mathcal{U}(\mathcal{S}(0,1))}\left[ \left| \phi(x+\sigma v) + \epsilon(x+\sigma v) - \phi(x) - \epsilon(x) \right| \right]\\
&\qquad \le{}  \frac{n}{N\sigma} \left(\nabla \phi(x)^\intercal \sigma {u} + \frac{L \|\sigma {u}\|^2}{2} + 2\epsilon_f \right) + \frac{n}{N\sigma} E}{\mbox{\boldmath$E$}{E}_{v \sim \mathcal{U}(\mathcal{S}(0,1))} \left[\nabla \phi(x)^\intercal \sigma v + \frac{L \|\sigma v \|^2}{2} + 2\epsilon_f \right] \\
&\qquad \le{}  \frac{n}{N}(2 \|\nabla f(x)\| + L \sigma + \frac{4 \epsilon_f}{\sigma}),
\end{align*}
for any $u \sim \mathcal{U}(\mathcal{S}(0,1))$.
The \emph{matrix variance statistic} of $g(x) - \nabla F(x)$ is
\begin{align*}
&v(g(x) - \nabla F(x)) \\
&\qquad ={} \max \left\{ \| E}{\mbox{\boldmath$E$}{E}\left[(g(x) - \nabla F(x))(g(x) - \nabla F(x))^\intercal \right] \|, E}{\mbox{\boldmath$E$}{E}\left[(g(x) - \nabla F(x))^\intercal (g(x) - \nabla F(x)) \right] \right\} \\
&\qquad \le{} \max \left\{ \frac{1}{N} \left( \frac{3n}{n+2} \|\nabla \phi(x)\|^2 + \frac{nL^2\sigma^2}{4} + \frac{4n \epsilon_f^2}{\sigma^2}  + 2nL\epsilon_f \right), \frac{n^2}{N} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{L^2\sigma^2}{4} + \frac{4\epsilon_f^2}{\sigma^2} + 2 L \epsilon_f \right) \right\} \\
&\qquad ={} \frac{n^2}{N} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{L^2\sigma^2}{4} + \frac{4\epsilon_f^2}{\sigma^2} + 2 L \epsilon_f \right).
\end{align*}
By Bernstein's inequality, we have
\begin{align*}
&E}{\mbox{\boldmath$E$}{P}(\|g(x) - \nabla F(x)\| \ge r) \\
&\qquad \le{} (n+1) \exp\left( \frac{-r^2/2}{v(g(x) - \nabla F(x)) + \frac{nr}{3N} (2 \|\nabla f(x)\| + L \sigma + \frac{4\epsilon_f}{\sigma} )} \right) \\
&\qquad \le{} (n+1) \exp\left( \frac{-r^2/2}{\frac{n^2}{N} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{L^2\sigma^2}{4} + \frac{4\epsilon_f^2}{\sigma^2} + 2 L \epsilon_f \right) + \frac{nr}{3N} (2 \|\nabla f(x)\| + L \sigma + \frac{4\epsilon_f}{\sigma})} \right).
\end{align*}
In order to ensure that $E}{\mbox{\boldmath$E$}{P}(\|g(x) - \nabla F(x)\| \ge r) \le \delta$, for some $\delta \in (0,1)$, we require that
\begin{align*}
(n+1) \exp\left( \frac{-r^2/2}{\frac{n^2}{N} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{L^2\sigma^2}{4} + \frac{4\epsilon_f^2}{\sigma^2} + 2 L \epsilon_f \right) + \frac{nr}{3N} (2 \|\nabla f(x)\| + L \sigma + \frac{4\epsilon_f}{\sigma})} \right) \le \delta,
\end{align*}
from which we conclude that
\begin{align*}
N \ge \left[ \frac{2n^2}{r^2} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{L^2\sigma^2}{4} + \frac{4\epsilon_f^2}{\sigma^2} + 2 L \epsilon_f  \right)  + \frac{2n}{3r} \left( 2 \|\nabla f(x)\| + L \sigma + \frac{4\epsilon_f}{\sigma} \right) \right] \log \frac{n+1}{\delta}.
\end{align*}

For the cBSG case, note that
\begin{align*}
E}{\mbox{\boldmath$E$}{E}_{u_i \sim \mathcal{U}(\mathcal{S}(0,1))} \left[\frac{n}{N} \frac{f(x+\sigma u_i) - f(x-\sigma u_i)}{2\sigma} u_i - \frac{1}{N} \nabla F(x)\right] &= 0,
\end{align*}
and
\begin{align*}
&\left\| \frac{n}{N} \frac{f(x+\sigma {u}) - f(x-\sigma {u})}{2\sigma} {u}  - \frac{1}{N} \nabla F(x) \right\| \\
&\qquad \le{}  \frac{n}{2N\sigma} \left| f(x+\sigma u) - f(x-\sigma {u})\right|  \|u\| + \frac{n}{2N\sigma} E}{\mbox{\boldmath$E$}{E}_{v \sim \mathcal{U}(\mathcal{S}(0,1))}\left[ \left| f(x+\sigma v) - f(x-\sigma v) \right| \|v\| \right]\\
&\qquad ={}  \frac{n}{2N\sigma} \left| \phi(x+\sigma u) + \epsilon(x+\sigma u) - \phi(x-\sigma u) - \epsilon(x-\sigma u) \right| \\
&\qquad \qquad +  \frac{n}{2N\sigma} E}{\mbox{\boldmath$E$}{E}_{v \sim \mathcal{U}(\mathcal{S}(0,1))}\left[ \left| \phi(x+\sigma v) + \epsilon(x+\sigma v) - \phi(x) - \epsilon(x) \right| \right]\\
&\qquad \le{}  \frac{n}{2N\sigma} \left(2\nabla \phi(x)^\intercal \sigma {u} + \frac{M \|\sigma {u}\|^3}{3}  + 2\epsilon_f \right) + \frac{n}{2N\sigma} E}{\mbox{\boldmath$E$}{E}_{v \sim \mathcal{U}(\mathcal{S}(0,1))} \left[2\nabla \phi(x)^\intercal \sigma {u} + \frac{M \|\sigma {u}\|^3}{3}  + 2\epsilon_f \right] \\
&\qquad \le{}  \frac{n}{N} \left(2 \|\nabla \phi(x)\| + \frac{M \sigma^2}{3} + \frac{2 \epsilon_f}{\sigma} \right),
\end{align*}
for any $u \sim \mathcal{U}(\mathcal{S}(0,1))$.
The \emph{matrix variance statistic} of $g(x) - \nabla F(x)$ is
\begin{align*}
&v(g(x) - \nabla F(x)) \\
&\qquad ={} \max \left\{ \| E}{\mbox{\boldmath$E$}{E}\left[(g(x) - \nabla F(x))(g(x) - \nabla F(x))^\intercal \right] \|, E}{\mbox{\boldmath$E$}{E}\left[(g(x) - \nabla F(x))^\intercal (g(x) - \nabla F(x)) \right] \right\} \\
&\qquad \le{} \max \left\{ \frac{1}{N} \left( \frac{3n}{n+2} \|\nabla \phi(x)\|^2 + \frac{n M^2 \sigma^4}{36} + \frac{n \epsilon_f^2}{\sigma^2} + \frac{n M\sigma \epsilon_f}{3} \right), \frac{n^2}{N} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{M^2\sigma^4}{36} + \frac{\epsilon_f^2}{\sigma^2} + \frac{M\sigma \epsilon_f}{3} \right) \right\} \\
&\qquad ={}  \frac{n^2}{N} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{M^2\sigma^4}{36} + \frac{\epsilon_f^2}{\sigma^2} + \frac{M\sigma \epsilon_f}{3} \right) .
\end{align*}
By Bernstein's inequality, we have
\begin{align*}
&E}{\mbox{\boldmath$E$}{P}(\|g(x) - \nabla F(x)\| \ge r) \\
&\qquad \le{} (n+1) \exp\left( \frac{-r^2/2}{v(g(x) - \nabla F(x)) + \frac{nr}{3N} \left(2 \|\nabla \phi(x)\| + \frac{M \sigma^2}{3} + \frac{2 \epsilon_f}{\sigma} \right)} \right) \\
&\qquad \le{} (n+1) \exp\left( \frac{-r^2/2}{\frac{n^2}{N} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{M^2\sigma^4}{36} + \frac{\epsilon_f^2}{\sigma^2} + \frac{M\sigma \epsilon_f}{3} \right) + \frac{nr}{3N} \left(2 \|\nabla \phi(x)\| + \frac{M \sigma^2}{3} + \frac{2 \epsilon_f}{\sigma} \right)} \right).
\end{align*}
In order to ensure that $E}{\mbox{\boldmath$E$}{P}(\|g(x) - \nabla F(x)\| \ge r) \le \delta$, for some $\delta \in (0,1)$, we require that
\begin{align*}
(n+1) \exp\left( \frac{-r^2/2}{\frac{n^2}{N} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{M^2\sigma^4}{36} + \frac{\epsilon_f^2}{\sigma^2} + \frac{M\sigma \epsilon_f}{3} \right) + \frac{nr}{3N} \left(2 \|\nabla \phi(x)\| + \frac{M \sigma^2}{3} + \frac{2 \epsilon_f}{\sigma} \right)} \right) \le \delta,
\end{align*}
from which we conclude that
\begin{align*}
N \ge \left[ \frac{2n^2}{r^2} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{M^2\sigma^4}{36} + \frac{\epsilon_f^2}{\sigma^2} + \frac{M\sigma \epsilon_f}{3} \right)  + \frac{2n}{3r} \left( 2 \|\nabla \phi(x)\| + \frac{M \sigma^2}{3} + \frac{2 \epsilon_f}{\sigma} \right) \right] \log \frac{n+1}{\delta}.
\end{align*}
\end{proof}

Now, with bounds for both terms in \eqref{eq:2terms_sphere}, we can bound $\|g(x) - \nabla \phi(x)\|$, in probability.

\begin{theorem} \label{thm:prob_bnd_sphere_smoothed_bern}
Suppose that Assumption  \ref{assum:lip_cont} holds and  $g(x)$ is calculated via \eqref{eq:BSG}.
If
\begin{align*}
	N \ge \left[ \frac{2n^2}{r^2} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{L^2\sigma^2}{4} + \frac{4\epsilon_f^2}{\sigma^2} + 2 L \epsilon_f  \right)  + \frac{2n}{3r} \left( 2 \|\nabla \phi(x)\| + L \sigma + \frac{4\epsilon_f}{\sigma} \right) \right] \log \frac{n+1}{\delta},
\end{align*}
then, for all $x \in E}{\mbox{\boldmath$E$}{R}^n$ and $r>0$,
\begin{align}	\label{eq:BSG_thm}
	\|g({x}) - \nabla \phi({x})\| \leq L \sigma + \frac{n \epsilon_f}{\sigma} + r.
\end{align}
with probability at least $1 - \delta$.

Alternatively, suppose that Assumption  \ref{assum:lip_cont_hess} holds and  $g(x)$ is calculated via \eqref{eq:cBSG}.
If
\begin{align*}
	N \ge \left[ \frac{2n^2}{r^2} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{M^2\sigma^4}{36} + \frac{\epsilon_f^2}{\sigma^2} + \frac{M\sigma \epsilon_f}{3} \right)  + \frac{2n}{3r} \left( 2 \|\nabla \phi(x)\| + \frac{M \sigma^2}{3} + \frac{2 \epsilon_f}{\sigma} \right) \right] \log \frac{n+1}{\delta},
\end{align*}
then, for all $x \in E}{\mbox{\boldmath$E$}{R}^n$ and $r>0$,
\begin{align}	\label{eq:cBSG_thm}
	\|g({x}) - \nabla \phi({x})\| \leq M \sigma^2 + \frac{n \epsilon_f}{\sigma}+ r.
\end{align}
with probability at least $1 - \delta$.
\end{theorem}

\begin{proof} The proof for the first part \eqref{eq:BSG_thm} is a straightforward combination of the bound in \eqref{eq:BSG_bound1} and the result of the first part of Lemma \ref{lem:prob_bnd_sphere_smoothed_bern}. The proof for the second part \eqref{eq:cBSG_thm} is a straightforward combination of the bound in \eqref{eq:cBSG_bound1} and the result of the second part of Lemma \ref{lem:prob_bnd_sphere_smoothed_bern}.
\end{proof}

In Theorem \ref{thm:prob_bnd_sphere_smoothed_bern} one should notice the improved dependence of the size of the sample set $N$ on the probability $\delta$ as compared to Theorem \ref{thm:prob_bnd_smoothed}. While Bernstein's inequality
does not apply in the case of the Gaussian smoothed gradient, there may be other ways to establish a better dependence on $\delta$. However, the dependence on $n$ in all cases is linear, which as we have shown for the GSG case is a necessary dependence.  A similar lower bound result for BSG can be derived analogously.

Using the results of Theorem \ref{thm:prob_bnd_sphere_smoothed_bern}, as before, we derive bounds on $\sigma$ and $N$ that ensure that \eqref{eq:theta_cond} holds with  probability $1-\delta$. To ensure \eqref{eq:theta_cond}, with probability $1-\delta$, using  Theorem \ref{thm:prob_bnd_sphere_smoothed_bern} we want the following to hold
\begin{align}
	  L \sigma +  \frac{n \epsilon_f}{\sigma} &\leq \lambda \theta \|\nabla \phi({x})\| \label{eq:ball1},\\
	 r &\leq  (1-\lambda) \theta \|\nabla \phi({x})\|, \label{eq:ball2}
\end{align}
for some $\lambda\in (0,1)$.

Let us first consider $g(x)$ calculated via \eqref{eq:BSG}. As before, to ensure that \eqref{eq:ball1} holds, we impose the following conditions,
 \begin{align*
	\sqrt{ \frac{n \epsilon_f}{L}}\leq \sigma \leq \frac{\lambda\theta\|\nabla \phi(x)\|}{2L }, \quad \|\nabla \phi(x)\|\geq \frac{2\sqrt{nL\epsilon_f}}{\lambda\theta}.
 \end{align*}
Now using these bounds and substituting $r = (1-\lambda) \theta \|\nabla \phi({x})\|$ into the first bound on $N$ in Theorem \ref{thm:prob_bnd_sphere_smoothed_bern} we have
\begin{align} \label{eq:BSG_nbound}
	&\left[ \frac{2n^2}{r^2} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{L^2\sigma^2}{4} + \frac{4\epsilon_f^2}{\sigma^2} + 2 L \epsilon_f  \right)  + \frac{2n}{3r} \left( 2 \|\nabla \phi(x)\| + L \sigma + \frac{4\epsilon_f}{\sigma} \right) \right] \log \frac{n+1}{\delta}\\
	& \qquad \leq \left[ \frac{2n}{\theta^2}\frac{1}{(1-\lambda)^2} + \left( \frac{n^2}{8} + 2 + n\right)  \frac{\lambda^2}{(1-\lambda)^2} + \frac{4n}{3 \theta}\frac{1}{ (1-\lambda)} + \left(\frac{n}{3} + \frac{4}{3}\right)\frac{\lambda}{ (1-\lambda)}\right] \log \frac{n+1}{\delta} \nonumber.
\end{align}

As before, we are interested in making the lower bound on $N$ to scale at most linearly with $n$.  Thus, to achieve this and to simplify the expression we choose $\lambda=\frac{1}{2\sqrt{n}}$ so that $\frac{ \lambda^2}{ (1-\lambda)^2}\leq \frac{1}{n}$, for all $n$. Then, using that  $\frac{1}{(1-\lambda)^2}\leq \frac{n}{(\sqrt{n}-1)^2}$ and  $\frac{1}{n}\leq 1$  the above expression is bounded by
\begin{align}\label{eq:BSG_nbound_simple}
 \left[\frac{2n }{\theta^2 }\frac{n}{(\sqrt{n}-1)^2} + \frac{n}{8}  + 3 + \frac{4n}{3 \theta}\frac{\sqrt{n}}{(\sqrt{n}-1)} + \frac{\sqrt{n}}{3} + \frac{4}{3} \right] \log \frac{n+1}{\delta}.
\end{align}

This implies that by choosing $N$ at least as large as the value of \eqref{eq:BSG_nbound_simple}
we ensure that \eqref{eq:ball2} holds.

We now summarize  the   result  for the gradient approximation computed via \eqref{eq:BSG}, using the fact that $\lambda =  \frac{1}{2\sqrt{n}}$.
\begin{corollary} \label{corr:BSG}
Suppose that Assumption \ref{assum:lip_cont}  holds, $n>1$
and $g(x_k)$ is computed via  \eqref{eq:BSG}  with $N$ and $\sigma$ satisfying
\begin{gather*}
N \geq \left[\frac{2n }{\theta^2 }\frac{n}{(\sqrt{n}-1)^2}+ \frac{n}{8}   + \frac{4n}{3 \theta} \frac{\sqrt{n}}{(\sqrt{n}-1)} + \frac{\sqrt{n}}{3}+ \frac{13}{3}  \right] \log \frac{n+1}{\delta},\\
	\sqrt{ \frac{n \epsilon_f}{L}}\leq \sigma \leq \frac{\theta\|\nabla \phi(x)\|}{4\sqrt{n}L }, \quad \|\nabla \phi(x)\|\geq \frac{4n\sqrt{L\epsilon_f}}{\theta},
\end{gather*}
 then \eqref{eq:theta_cond} holds with  probability $1-\delta$.
\end{corollary}

We now derive the analogous bounds on $N$ and $\sigma$ for the case when $g(x)$ is calculated via \eqref{eq:cBSG}. To ensure \eqref{eq:theta_cond}, with probability $1-\delta$, using  Theorem \ref{thm:prob_bnd_sphere_smoothed_bern} we want the following to hold
\begin{align}
	 M \sigma^2 +  \frac{n \epsilon_f}{\sigma} &\leq \lambda \theta \|\nabla \phi({x})\| \label{eq:sphere3},\\
	 r &\leq  (1-\lambda) \theta \|\nabla \phi({x})\|, \label{eq:sphere4}
\end{align}
for some $\lambda\in (0,1)$. In order to ensure that \eqref{eq:sphere3} holds, we use the same logic as was done for Central Finite Differences in Section \ref{sec:fd}. Namely, we require the following,
 \begin{align*
	\sqrt[3]{ \frac{n \epsilon_f}{M}}\leq \sigma \leq \sqrt{\frac{\lambda\theta\|\nabla \phi(x)\|}{2M }}, \quad \|\nabla \phi(x)\|\geq \frac{2\sqrt[3]{n^2M\epsilon_f^2}}{\lambda\theta}.
 \end{align*}
Now using these bounds and setting $r = (1-\lambda) \theta \|\nabla \phi({x})\|$ into the second bound on $N$ in Theorem \ref{thm:prob_bnd_smoothed} we have
\begin{align*}
	 &\left[ \frac{2n^2}{r^2} \left( \frac{\|\nabla \phi(x)\|^2}{n} + \frac{M^2\sigma^4}{36} + \frac{\epsilon_f^2}{\sigma^2} + \frac{M\sigma \epsilon_f}{3} \right)  + \frac{2n}{3r} \left( 2 \|\nabla \phi(x)\| + \frac{M \sigma^2}{3} + \frac{2 \epsilon_f}{\sigma} \right) \right] \log \frac{n+1}{\delta}\\
& \qquad \leq \left[ \frac{2n}{\theta^2}\frac{1}{(1-\lambda)^2} + \left( \frac{n^2}{72} + \frac{1}{2} + \frac{n}{6}\right)  \frac{\lambda^2}{(1-\lambda)^2} + \frac{4n}{3 \theta}\frac{1}{ (1-\lambda)} + \left(\frac{n}{9} + 2\right)\frac{\lambda}{ (1-\lambda)}\right] \log \frac{n+1}{\delta}.
\end{align*}
As before, we are interested in making the lower bound on $N$ to scale at most linearly with $n$.  Thus, to achieve this and to simplify the expression we choose $\lambda$ such that $\frac{ \lambda^2}{ (1-\lambda)^2}\leq \frac{1}{n}$, which,  implies that $\lambda\leq\frac{1}{\sqrt{n}} $. Then, using again the fact that  $\frac{1}{(1-\lambda)^2}\leq \frac{n}{(\sqrt{n}-1)^2}$ and $\frac{1}{n}\leq 1$  the above expression is bounded by
\begin{align*}
 \left[\frac{2n }{\theta^2 }\frac{n}{(\sqrt{n}-1)^2} + \frac{n}{72}  + \frac{2}{3} + \frac{4n}{3 \theta}\frac{\sqrt{n}}{(\sqrt{n}-1)} + \frac{\sqrt{n}}{9} + 2 \right] \log \frac{n+1}{\delta}.
	 \end{align*}

We now summarize  the   result  for the gradient approximation computed via \eqref{eq:cBSG}, using the fact that $\lambda =  \frac{1}{2\sqrt{n}}$.
\begin{corollary} \label{corr:cBSG}
Suppose that Assumption \ref{assum:lip_cont_hess} holds, $n>1$ and $g(x_k)$ is computed via  \eqref{eq:cBSG}  with $N$ and $\sigma$ satisfying
\begin{gather*}
N \geq  \left[\frac{2n }{\theta^2 }\frac{n}{(\sqrt{n}-1)^2} + \frac{n}{72}  + \frac{8}{3} + \frac{4n}{3 \theta}\frac{\sqrt{n}}{(\sqrt{n}-1)} + \frac{\sqrt{n}}{9} \right] \log \frac{n+1}{\delta},\\
	\sqrt[3]{ \frac{n \epsilon_f}{M}}\leq \sigma \leq \sqrt{\frac{\theta\|\nabla \phi(x)\|}{4\sqrt{n}M }}, \quad \|\nabla \phi(x)\|\geq \frac{4\sqrt[3]{n^{7/2}M\epsilon_f^2}}{\theta},
\end{gather*}
then \eqref{eq:theta_cond} holds with  probability $1-\delta$.
\end{corollary}

redpajama_set_name: RedPajamaArXiv


When you are a patient at Dentistry in the Pines we want you to know your dental health is our main concern. We pride ourselves on making you feel at home while providing top-notch dental care. Please feel free to contact us with any questions or to schedule an appointment.
I have been a patient of hers for over 10 years. She and her staff are very friendly. They listen to my concerns and address the problems. I feel she is honest and up front and I have always recommended her to friends looking for a new dentist!
I feel fortunate to have found this dental practice. Dr. Mirza and her staff are professional, thorough. and compassionate. I have always had positive experiences here, and highly recommend this practice.


text:
Cuiabá este un capitala statului Mato Grosso (MT), Brazilia. Acest oraș este localizat în centrul Americii de Sud și împreună cu municipiul învecinat, Várzea Grande formează principala zonă metropolitană a statului.

Orasul a fost fondat în 1719 d.Hr., în timpul goanei după aur, a devenit capitala statului în 1818. Orașul este un centru comercial al acestei zone vaste în care se practică creșterea vitelor și agricultura. Dezvoltarea economică a fost îngreunată de izolare municipiului și de lipsa forței de muncă. Șlepurile rămân un mijloc important de transport.

Cuiaba este în centrul unei zone urbane, care include, de asemenea, al doilea cel mai mare oraș al statului, Várzea Grande. Termocentrale și hidrocentralele situate în zonă s-au extins după terminarea unei conducte de gaze naturale ce face legătura cu Bolivia în 2000. În orașul își are sediul Universitatea Federală din Mato Grosso și aici se găsește cel mai mare stadion de fotbal din statul Mato Grosso, Arena Pantanal.

Orasul este cunoscut și sub numele de "Poarta Sudică a Amazonului".

Climă

Galerie

Referințe

Cuiabá
Municipii din Mato Grosso

redpajama_set_name: RedPajamaWikipedia


text:
Richard David Barnett CBE, angleško-judovski arheolog, častnik, akademik in pedagog, * 23. januar 1909, † 29. julij 1986.

Med drugo svetovno vojno je bil obveščevalni častnik na Bližnjem Vzhodu.

Deloval je v Britanskem muzeju in bil predavatelj na Hebrejski univerzi v Jeruzalemu.

Leta 1962 je postal član Britanske akademije.

Sklici in opombe

Glej tudi
 seznam angleških arheologov
 seznam angleških akademikov
 seznam članov Britanske akademije

Angleški obveščevalci
Angleški častniki
Angleški arheologi
Angleški akademiki
Angleški Judje
Veterani druge svetovne vojne
Predavatelji na Hebrejski univerzi v Jeruzalemu
Poveljniki reda britanskega imperija
Člani Britanske akademije
Angleški univerzitetni učitelji


The 2010–11 FA Cup Qualifying Rounds opened the 130th season of competition in England for 'The Football Association Challenge Cup' (FA Cup), the world's oldest association football single knockout competition. A total of 759 clubs were accepted for the competition, down three from the previous season's 762.
The schedule of the 2010-11 FA Cup Qualifying Rounds, as announced by The FA.


text:
On to unfinished business
The quest for an industrial strategy: Trudeau wants to outdo Sir John A.
Ian Anderson June 29 1981
On to unfinished business Ian Anderson June 29 1981
There sage in was the perhaps way Pierre a subtle Trudeau mestooled his classic 1959 Mercedes ragtop past the glinting camera lenses on the way to joining his cabinet. Al-
most exactly two years ago was the last time he had driven it publicly—and then it was the symbol of his newfound freedom as he handed over power to Joe Clark at Government House after 11 contentious years as prime minister. Now he was meeting his cabinet for the annual summer think-in at Meach Lake, in the peaceful Gatineau hills north of Ottawa. And now he could bask in the pleasure of good opinion polls, a happy Liberal party and the prospect of a summer and autumn of international exposure. Fresh from the party's policy conference, policy chairman Lorna Marsden was gushing her praise of Trudeau's newfound activism. "Boy, the party likes it," said the University of Toronto sociology professor. "I don't think I've ever the membership
so happy." As for Trudeau's promised retirement, Marsden brushed it off as "the farthest thing from our minds." From all indications it may also be the farthest thing from Trudeau's. Any disappointment he felt at the Supreme Court of Canada's decision to recess for the summer before rendering its ruling on the legality of Trudeau's constitutional proposals spilled out Thursday in vituperative exchanges with the "morally bankrupt" Joe Clark and "jerk" John Crosbie. But he left the hubbub of the House behind to dash to Europe this week to discuss next month's economic summit in Ottawa, the most prestigious gathering of foreign leaders he has ever hosted.
The Meach Lake sessions used to loom much larger in the summer's political calendar. They were designed to set the government's priorities for the fall and winter. While the insiders talked boldly this spring of Trudeau's intention to devote his government's
energies toward designing an industrial strategy for the country, such intentions seem thwarted by tight budgets and political realities. There lingers the suspicion, however, that Trudeau and his principal ministers—Allan MacEachen, Marc Lalonde and Jean Chrétien—still intend to leave their mark on the country's economy in the way Sir John A. Macdonald did with the only really coherent industrial strategy the country has had—the century-old National Policy, which raised tariff barriers and impeded western industrial development in favor of promoting manufacturing in Central Canada.
With all the talk of an industrial grand design, businessmen are naturally spooked. "Everyone's sitting out there wondering what's going to come down from Ottawa," says the Canadian Manufacturers' Association's executive vice-president, Larry Thibault. "We're all just guessing." At the front of their minds is the ease with which Ottawa bulled through its National Energy Program (NEP), an unprecedented piece of industrial intervention which successfully tilted the game in favor of Canadian companies. But Ottawa seems more hesitant in taking the next step, despite its belief that there is a strong underlying current of public support. "Industrial what?" giggles a Liberal backbencher who confides that the caucus has no idea what Industry Minister Herb Gray is concocting to replace the $2.75-billion industrial policy proposal aborted by the cabinet last fall. "Yes, we could 3 afford it," suggests a o senior finance departement bureaucrat. "But t; not without a lot of privation in other areas." That message may - seem like small consolation to business executives whose bruised tones indicate they feel like the rubber ball at the end of the Wham-0 paddle. Government insiders indicate that there is still a desire by key members of Trudeau's inner circle to alter radically the structure of Canadian industry—particularly in terms of exports, research and development, upgrading of primary resources and foreign ownership. As Marsden puts it, there is in the party a "spirit for making some change in the country." But there exists no plan for doing it, aside from highly interventionist proposals from Herb Gray.
For the moment, however, cabinet appears bent more toward the softer,
piecemeal line promoted by Senator Horace Andrew (Bud) Olsen, the stoopshouldered boss of the 100 bureaucrats at the tiny, powerful ministry of state for economic development. The Albertan rancher and former Social Créditer wears the velvet glove when he promises business there will be no NEP-style intervention—but only so long as "companies do their job and invest in Canada to maximize the benefits to Canadians." That message has also been conveyed to business by consultants such as Morrey Ewing of the Canada Consulting Group. A graduate of the Harvard business school, Ewing suggests business study the governmental concerns behind the NEP and determine how it can lead Ottawa toward mutually acceptable goals, rather than stay taciturn and be dragged. With Italy and Britain, Canada is stuck in the so-called "second tier" of industrial countries, having a limited domestic technology base and, according to the Science Council of Canada, scant chance of joining the United States and Japan in tier one. In 1980,
Canada imported nearly $18 billion more manufactured goods than it exported, and the Science Council warned the government last fall that "the dismal trend in this trade is of profound concern."
In this atmosphere Ewing touts as Ottawa's "heroes" those few foreignowned companies, such as Westinghouse and Black and Decker, that have allowed their Canadian subsidiaries to develop a world market for their products. In this manner they enlarge the Canadian content of their goods and cushion their factories against downturns in the small Canadian economy. In its own self-interest, says Ewing, business should adapt itself to meeting government economic goals—on terms satisfactory to business. "One of the things business needs to understand is that government is like any other market," he proposes. "You have to appeal to it. You have to be there first."
Given the present feistiness of the Trudeau Liberals, such conciliatory advice may be hard for business to swallow. Trudeau himself has talked recently of the "two solitudes" of business and government. This has been echoed by Tom d'Aquino, a former Trudeau aide who now sits as president of the Business Council on National Issues— an umbrella group of the country's most senior chief executives. D'Aquino's sermon to business is to take an approach "strongon statesmanship, with an avoidance of the traditional clattering of special-interest groups." Such advice will be put to the test this fall, as Ottawa inevitably turns its gaze toward industrial change. The business community is well warned to remember Petro-Canada Chairman Bill Hopper's advice to the government—that the wheel that squeaks loudest gets the most grease. And no one should be surprised when Ottawa's economic ministers start squeaking much louder than they do now.
Return of the prophet
June 1981 By Mark Czarnecki
Economies of scale in a minor key
June 1981 By Anthony Whittingham, David Coates
June 1981 By BARBARA MATTHEWS
Just one room at the top
June 1981 By Ken Becker
Pouring a new mould for world aid
June 1981 By Elizabeth Gray
A Canadian of value
June 1991 By GLEN ALLEN
A soft-spoken chief
National Notes
The boss of all bosses
August 1981 By IAN ANDERSON
Ottawa Anne Murray is a favorite, so is Star Wars. Illegal copying of mu-
Home movies of a darker kind
June 1981 By IAN ANDERSON
Big Oil extends its reach
January 1983 By IAN ANDERSON

redpajama_set_name: RedPajamaCommonCrawl


text:
Yes, Patrick Warburton Commits All That Lemony Snicket Narration to Memory
"A Series of Unfortunate Events" — and those top-notch monologues from its "Seinfeld" alum — returns to Netflix at midnight Thursday
Tony Maglio | March 29, 2018 @ 2:39 PM
Netflix's 'A Series of Unfortunate Events'
As a show title, "Lemony Snicket's A Series of Unfortunate Events" is a mouthful — and so are actor Patrick Warburton's monologues on the excellent Netflix series. (Which ironically often beg you not to watch the excellent Netflix series.)
Ahead of the Season 2 release Thursday night, we had a couple of questions for the man working with arguably the best and most informative dialogue on TV. Like, has all of this SAT prep-esque narration helped Warburton's own vocabulary as much as it has expanded ours?
"Lemony, he's a writer and has a vocabulary, but he also has a way of putting things and speaking that are … about an unusual placement of the ideas," Warburton told TheWrap. "It's not the way I would talk. So, sometimes it could get to be a bit of a challenge learning some of those monologues and attaching the ideas and the thoughts in the way that Lemony does, as opposed to the way I would."
Also Read: Lemony Snicket Apologizes for Crass Comments to Female Authors, Calls Them 'Lapses in Taste'
Obviously, the show's script supervisors help with the nuance. That was a real service while shooting next year's Season 3, Warburton said, recalling a time he got especially tripped up rattling off tough opera titles and confusing composer names.
There's another trick Warburton could use — and it was even offered at one point — but relying on cue cards for anything outside of a news broadcast would be "an absolute no-no," the "Seinfeld" alum told us.
"In the industry, I don't know what type of street cred I have as an actor," he said, "but I will tell you from my early days in theater and just workshopping things, that would be sacrilege to me."
Also Read: 'A Series of Unfortunate Events' Season 2 Trailer: Baudelaires Meet Miserable Counterparts (Video)
"A Series of Unfortunate Events" returns to Netflix for Season 2 at midnight Thursday. The streaming series is scheduled to end after a third season, which is set for 2019.
'Altered Carbon' Star Dichen Lachman StudioWrap Portraits (Exclusive Photos)
Dichen Lachman, "Altered Carbon"
Photographed by Elisabeth Caren for TheWrap
Actress stops by TheWrap to talk new Netflix series