\vspace{-4mm}
\section{Preliminaries}
\label{sec:prelim}
\vspace{-5pt}
In this section, we present definitions and preliminary results needed throughout our analysis.

Following \cite{nesterov2017random,bach2016highly}, we introduce the following classes of Lipschitz and smooth functions.

\begin{defn}[Lipschitz functions]
	The class of Lipschtiz-continuous functions $C^{0,0}$ satisfy: for any $f \in C^{0,0}$, $|f(x) - f(y)| \le L_0 \|x-y\|, ~\forall x,y\in \mathbb{R}^d$,


	for some Lipschitz parameter $L_0>0$. The class of smooth functions $C^{1,1}$ satisfy: for any $f \in C^{1,1}$, $\|\nabla f(x) - \nabla f(y)\| \le L_1\|x-y\|, ~\forall x,y\in \mathbb{R}^d,$


	for some Lipschitz parameter $L_1>0$.
\end{defn}


In ZO, the objective is to estimate the first-order gradient of a function using zeroth-order oracles. Necessarily, we need to perturb the function around the current point along all the directions uniformly in order to estimate the gradient. This motivates us to consider the Gaussian-smoothed version of the function $f$ as introduced in \cite{nesterov2017random}, $f_\delta(x) := \mathbb{E}_{u\sim \mathcal{N}(0,1)}[f(x+\delta u)]$,


where the coordinates of the vector $u$ are i.i.d standard Gaussian random variables. The following bounds on the approximation error of the function $f_\delta(x)$ have been developed in \cite{nesterov2017random}.
\begin{lem}[Gaussian approximation]
	\label{lem:GaussianApprox}
	Consider a function $f$ and its Gaussian-smoothed version $f_\delta$. It holds that 
	\begin{align*}
	|f_\delta(x)-f(x)|\le
	\begin{cases}
	\delta L_0\sqrt{d}, ~\text{if}~f\in C^{0,0}, \\
	\delta^2 L_1 d, ~\text{if}~f\in C^{1,1},
	\end{cases} \text{and }
	\|\nabla f_\delta(x)- \nabla f(x)\|\le \delta L_1 (d+3)^{3/2}, ~\text{if}~ f\in C^{1,1}.
	\end{align*}
\end{lem}
Moreover, the smoothed function $f_\delta(x)$ has the following nice geometrical property as proved in \cite{nesterov2017random}. 

\begin{lem}
	\label{lem:SmoothedFunctionLipschitiz}
	If function $f\in C^{0,0}$ is $L_0$-Lipschitz, then its Gaussian-smoothed version $f_\delta$ belongs to $C^{1,1}$ with Lipschitz constant $L_1 = \sqrt{d}\delta^{-1}L_0$.
\end{lem}

We also introduce the following notions of convexity.
\begin{defn}[Convexity]
	A continuously differentiable function $f: \mathbb{R}^d \to \mathbb{R}$ is called convex if for all $x,y \in \mathbb{R}^d$, $	f(x) \ge f(y) + \inner{x-y}{\nabla f(y)}.$


\end{defn}
{"config": "arxiv", "file": "2006.10820/preliminaries.tex"}