text:
\section{Proof for Theorem~\ref{thm:sfw-convex-wgc}}
In order to prove Theorem~\ref{thm:sfw-convex-wgc}, we require the following result from~\cite{nesterov2017random} for the zeroth-order case.
\begin{lemma}\textsc{\cite{nesterov2017random}}
Let the function $f$ has lipschitz continuous gradient with constant $L$. Consider the smoothed function $f_\nu (x) = \E_{u} [f(x+\nu u)]$ where $u\sim \normal(0, \mathbf{I}_d)$. Then for any $x\in\reals^d$,
	\begin{align}
		\E_u \left[\frac{f(x+\nu u) - f(x)}{\nu}u\right] & = \grad f_\nu (x)\label{eq:nestrov-first-moment}\\
		\norm{ \grad f_{\nu}(x) - \grad f(x) } &\leq \frac{\nu}{2}L(d+3)^{\frac{3}{2}}\label{eq:nestrov-bias}\\
		\frac{1}{\nu^2} \E_u [\{f(x+\nu u) - f(x)\}^2 \norm{u}^2] &\leq \frac{\nu^2}{2}L^2 (d+6)^3 + 2(d+4) \norm{\grad f(x)}^2. \label{eq:nestrov-second-moment}
	\end{align}
\end{lemma}

We now present the lemma below to bound the mean squared error for the zeroth-order gradient estimator.

\begin{lemma}\label{lem:zero_grad}
Under Assumption \ref{ass:constrained}, \ref{ass:smooth-F}, \ref{ass:WGC-moment}, we have
\begin{align}
	\label{eq:zero_grad_var}	\E \norm{\bar{G}_{\nu}^{t} - \grad f_{\nu}(x_{t-1}) }^2 & \leq \frac{ 4\rho L(d+4)(f(x_{t-1}) - f(x^*)) }{b_t} + \frac{\nu^2 L^2 (d+6)^3} {2b_t},\\
	\label{eq:zero_grad_mse}	\E \norm{\bar{G}_{\nu}^{t} - \grad f(x_{t-1}) }^2 & \leq \frac{ 4\rho L(d+4)(f(x_{t-1}) - f(x^*)) }{b_t} + \nu^2 L^2 (d+6)^3.
\end{align}
\end{lemma}

\begin{proof}
First note that by \eqref{eq:nestrov-first-moment}, we have
\begin{equation*}
	\E_{u,\xi} [\bar{G}_{\nu}^{t}] = \E_{u,\xi} [G_{t,j}] = \E_{u} \left[\frac{f(x_{t-1}+\nu u) - f(x_{t-1})}{\nu}u\right] = \grad f_\nu (x_{t-1}),
\end{equation*}

Then by using \eqref{eq:nestrov-second-moment} for $F$ instead of $f$, under Assumption \ref{ass:smooth-F}, \ref{ass:WGC-moment}, we can obtain
\begin{flalign*}
	\E_{u, \xi} \norm{\bar{G}_{\nu}^{t} - \grad f_{\nu}(x_{t-1}) }^2 & = \frac{1}{b_t} \E_{u,\xi} \norm{G_{t,j} - \grad f_{\nu}(x_{t-1})}^2\\
	&\leq \frac{1}{b_t} \E_{u, \xi} \norm {G_{t,j}}^2\\
	&\leq \frac{2(d+4)}{b_t}\E_{\xi} \norm{\grad F(x_{t-1}, \xi_{t,j})}^2 + \frac{\nu^2 L^2 (d+6)^3}{2b_t}\\
	&\leq  \frac{ 4\rho L(d+4)(f(x_{t-1}) - f(x^*)) }{b_t} + \frac{\nu^2 L^2 (d+6)^3} {2b_t}
\end{flalign*}
where the first inequality comes from the fact that the variance is less than the seocond moment.

To prove \eqref{eq:zero_grad_mse}, we decompose the mean squared error into the bias and the variance by utilizing the results \eqref{eq:zero_grad_var} and \eqref{eq:nestrov-bias}, i.e.,
\begin{flalign*}
	&& \E \norm{\bar{G}_{\nu}^{t} - \grad f(x_{t-1}) }^2  & = \E \norm{\bar{G}_{\nu}^{t} - \grad f_{\nu}(x_{t-1}) }^2 + \norm{\grad f_{\nu}(x_{t-1}) - \grad f(x_{t-1})}^2\\
	&& &\leq \frac{ 4\rho L(d+4)(f(x_{t-1}) - f(x^*)) }{b_t} + \frac{\nu^2 L^2 (d+6)^3} {2b_t} + \frac{\nu^2L^2(d+3)^{3}}{4}\\
	&& &\leq  \frac{ 4\rho L(d+4)(f(x_{t-1}) - f(x^*)) }{b_t} + \nu^2 L^2 (d+6)^3.
\end{flalign*}
\end{proof}

We also need the following simple result in our proof.
\begin{lemma}\label{gamma_recursive}
Assume that sequences $\{\phi_t\}_{t \ge 0} \ge 0$, $\{B_t\}_{t \ge 1}$, $\{\theta_t\}_{t \ge 1} \in [0,1]$ are given such that
\begin{equation}\label{rec1}
\phi_t \le (1-\theta_t) \phi_{t-1} + B_t.
\end{equation}
Then, we have
\[
\phi_T \le \Theta_T \left[\phi_0 + \sum_{t=1}^ T \frac{B_t}{\Theta_t}\right],
\]
where, for any $t \ge 2$,
\begin{equation}\label{def_gamma}
\Theta_t = \Theta_1 \prod_{k=2}^{t} (1-\theta_k), \quad \text{where} \ \ \Theta_1 = 1-\theta_1 \ \  \text{if} \ \ \theta_1<1, \quad \Theta_1 = 1 \ \  \text{if} \ \ \theta_1=1.
\end{equation}

\end{lemma}

\begin{proof}
Dividing both sides of \eqref{rec1} by $\Theta_t$, summing them up from $t=1$ to $t=T$, noting non-negativity of $\phi_t$ and \eqref{def_gamma}, we obtain the result.
\end{proof}

\begin{proof}[Proof for Theorem \ref{thm:sfw-convex-wgc}] For convenience, let $g_t$ be the gradient estimator at $t$ step. Thus, $g_t = \tilde{\grad}_t$ for the first order method while in the zeroth order setting $g_t = \bar{G}_{\nu}^t$.
\begin{flalign*}
    f(x_t) &\leq f(x_{t-1}) +  \inner{\grad f(x_{t-1}), x_t-x_{t-1}} + \frac{L}{2} \norm{x_t - x_{t-1}}^2\\
    &= f(x_{t-1}) +  \gamma_t\inner{\grad f(x_{t-1}), d_t-x_{t-1}} + \frac{L\gamma_t^2}{2} \norm{d_t- x_{t-1}}^2 \\
    &\leq f(x_{t-1}) + \gamma_t \inner{g_t, d_t-x_{t-1}} + \gamma_t\inner{\grad f(x_{t-1}) - g_t, d_t-x_{t-1}} + \frac{L D^2\gamma_t^2 }{2} \\
    &\leq f(x_{t-1}) + \gamma_t \inner{g_t, x^*-x_{t-1}} + \gamma_t\inner{\grad f(x_{t-1}) - g_t, d_t-x_{t-1}} + \frac{L D^2\gamma_t^2 }{2} \\%& \rhd \text{ by the optimality}\\
    &=  f(x_{t-1}) + \gamma_t \inner{\grad f(x_{t-1}), x^*-x_{t-1}} + \gamma_t\inner{\grad f(x_{t-1}) - g_t, d_t-x^*} + \frac{L D^2\gamma_t^2 }{2}\\
    &\leq f(x_{t-1}) + \gamma_t (f(x^*)- f(x_{t-1})) + \gamma_t\inner{\grad f(x_{t-1}) - g_t, d_t-x^*} + \frac{L D^2\gamma_t^2 }{2} \\%& \rhd \text{ by the convexity}\\
    &\leq f(x_{t-1}) + \gamma_t (f(x^*)- f(x_{t-1})) + \frac{\gamma_t}{2\beta}\norm{\grad f(x_{t-1}) - g_t}^2 + \frac{ D^2\gamma_t(L\gamma_t + \beta) }{2}.
\end{flalign*}
The last inequality comes from the Young's inequality: for any $\beta >0$,
\begin{align*}
    \inner{\grad f(x_{t-1}) - g_t, d_t-x^*} &\leq \frac{1}{2\beta} \norm{\grad f(x_{t-1}) - g_t}^2 + \frac{\beta}{2} \norm{d_t-x^*}^2 \\
    &\leq \frac{1}{2\beta} \norm{\grad f(x_{t-1}) - g_t}^2 + \frac{D^2\beta}{2}.
\end{align*}

Denote $\phi_t = f(x_t) - f(x^*)$. Substracting $f(x^*)$ from both sides of the inequality and taking the conditional expectation $\E[ \cdot | \mathcal{F}_{t-1}]$, we have
\begin{equation}\label{eq:fw-proof}
    \E[\phi_t | \mathcal{F}_{t-1}]  \leq (1-\gamma_t)\phi_{t-1} + \frac{\gamma_t}{2\beta} \E [\norm{\grad f(x_{t-1}) - g_t}^2 | \mathcal{F}_{t-1}] + \frac{D^2 \gamma_t (L\gamma_t + \beta)}{2}.
\end{equation}
 For the first-order gradient estimator $g_t = \tilde{\grad}_t$, we have the following bound for its variance under Assumption \ref{ass:WGC-variance}:
\begin{equation*}
	\E [\norm{\grad f(x_{t-1}) - \tilde{\grad}_t}^2 | \mathcal{F}_{t-1}] = \frac{1}{b_t} \E[\norm{\grad f(x_{t-1}) - \grad F(x_{t-1}, \xi_{t,j})}^2| \mathcal{F}_{t-1}]\leq \frac{2\rho L\phi_{t-1}}{b_t}.
\end{equation*}
Then by \eqref{eq:fw-proof}, we can obtain
\begin{equation*}
    \E[\phi_t|\mathcal{F}_{t-1}]\leq (1-\gamma_t)\phi_{t-1} + \frac{\gamma_t\rho L}{\beta b_t} \phi_{t-1} + \frac{D^2 \gamma_t (L\gamma_t + \beta)}{2}.
\end{equation*}
Let $\gamma_t = \frac{4}{t+3}, \beta = \rho L \gamma_t = \frac{4\rho L}{t+3}> 0, b_t = \lceil(t+3)/2\rceil$, then
\begin{equation}\label{eq:induction}
     \E[\phi_t | \mathcal{F}_{t-1}] \leq\left(1-\frac{2}{t+3}\right) \phi_{t-1} + \frac{8(\rho+1)LD^2}{(t+3)^2}.
\end{equation}

Now, letting $\theta_t = \frac{2}{t+3}$, it is easy to check that $\Theta_t = \frac{6}{(t+2)(t+3)}$ due to \eqref{def_gamma}. Hence, in the view of Lemma~\ref{gamma_recursive}, we have
\[
\E[\phi_t ] \leq \frac{6\phi_0}{(t+2)(t+3)} + \frac{8(\rho+1)LD^2}{t+3} \le \frac{2[\phi_0+4(\rho+1)LD^2]}{t+3}.
\]
The above inequality implies that to attain an $\epsilon$-optimal point, the total number of interations $T$ can be bounded by $\mathcal{O}(1/\epsilon).$ Hence, the number of the gradient calls $\sum_{t=1}^T b_t$ can be bounded by $\frac{T^2+7T}{4} = \mathcal{O}(T^2)$, and the number of calls to the linear minimization oracle immediately follows from this observation.

\noindent We now prove part (b). For the zeroth-order version, by \eqref{eq:zero_grad_mse} in Lemma \ref{lem:zero_grad} and \eqref{eq:fw-proof}, we can obtain
\begin{align*}
\E[\phi_t | \mathcal{F}_{t-1}] &\leq (1-\gamma_t)\phi_{t-1} + \frac{\gamma_t}{2\beta} \E [\norm{\grad f(x_{t-1}) - \bar{G}_\nu^t}^2 | \mathcal{F}_{t-1}] + \frac{D^2 \gamma_t (L\gamma_t + \beta)}{2}\\
    &\leq (1-\gamma_t)\phi_{t-1} + \frac{2\gamma_t\rho L(d+4)}{\beta b_t} \phi_{t-1} +  \frac{\gamma_t\nu^2 L^2 (d+6)^3}{2\beta} +\frac{D^2 \gamma_t (L\gamma_t + \beta)}{2}
\end{align*}
Let $\gamma_t = \frac{4}{t+3}, \beta = \gamma_t \rho L, b_t = (t+3)(d+4), \nu =  D(T+3)^{-1}(d+6)^{-3/2}\leq  D(t+3)^{-1}(d+6)^{-3/2}$, then we have
\begin{equation*}
\E[\phi_t | \mathcal{F}_{t-1}] \leq \left(1-\frac{2}{t+3}\right)\phi_{t-1}  + \frac{8(\rho+\rho^{-1}+1)}{(t+3)^2 LD^2}
\end{equation*}
Similarly, in the view of Lemma~\ref{gamma_recursive}, we obtain
\[
\E[f(x_t) - f(x^*)] \leq \frac{2[f(x_0) - f(x^*)]+8(\rho+\rho^{-1}+1)LD^2}{t+3}.
\]
The above inequality implies that to attain an $\epsilon$-optimal point, the total number of interations $T$ can be bounded by $\mathcal{O}(1/\epsilon).$ Hence, the number of calls to the zeroth-order oracles $2\sum_{t=1}^T b_t$ can be bounded by $(d+4)(T^2+7T) = \mathcal{O}(dT^2)$, and the number of calls to the linear minimization oracle immediately follows from this observation.
\end{proof}

\section{Proof of Theorem~\ref{thm:scgs-convex-wgc}}

\begin{proof}
[Proof of Theorem \ref{thm:scgs-convex-wgc}]
For convenience, let $g_t$ be the gradient estimator at $t$ step. Thus, $g_t = \tilde{\grad}_t$ for the first order method while in the zeroth order setting $g_t = \bar{G}_{\nu}^t$. First note that by the updates in Algorithm~\ref{alg:SFWSlideFandZ}, the convexity and the smoothness of $f$, we have

\begin{align}
	f(x_{t})  \leq & f(z_t) + \inner{\nabla f(z_t), x_t-z_t} +\frac{L}{2}\norm{x_t-z_t}^2\nonumber\\
	= &(1-\gamma_t) [f(z_{t})  +\inner{\nabla f(z_t), x_{t-1} - z_t }]+\gamma_t [f(z_{t}) + \inner{\nabla f(z_t), y_t-z_{t}}] +\frac{L\gamma_t^2}{2}\norm{y_t-y_{t-1}}^2\nonumber \\
	\leq & (1-\gamma_t) f(x_{t-1}) +\gamma_t [f(z_{t}) + \inner{\nabla f(z_t), y_t-z_{t}}] +\frac{L\gamma_t^2}{2}\norm{y_t-y_{t-1}}^2 \nonumber \\
	= &(1-\gamma_t) f(x_{t-1}) +\gamma_t [f(z_{t}) + \inner{\nabla f(z_t), y_t-z_{t}}] +\frac{\beta_t\gamma_t}{2}\norm{y_t-y_{t-1}}^2\nonumber \\
	& \quad - \frac{\gamma_t(\beta_t - L\gamma_t)}{2}\norm{y_t-y_{t-1}}^2. \label{eq:scgs-proof-1}
\end{align}

And by~\eqref{eq:acc_subprob}, we have
\begin{equation*}
\inner{g_t + \beta_t(y_t-y_{t-1}), y_t -x }\leq \eta_t, \quad \forall x\in\Omega.
\end{equation*}
Let $x=x^*$ in the above inequality. Then we have
\begin{align}
\frac{1}{2}\norm{y_t- y_{t-1}}^2 & = \frac{1}{2}\norm{y_{t-1}-x^*}^2 - \inner{y_{t-1}-y_{t}, y_t-x^*} - \frac{1}{2}\norm{y_t-x^*}^2 \nonumber\\
&\leq \frac{1}{2}\norm{y_{t-1}-x^*}^2 + \frac{1}{\beta_t}\inner{g_t, x^*-y_t} - \frac{1}{2}\norm{y_t-x^*}^2 + \frac{\eta_t}{\beta_t}. \label{eq:scgs-proof-2}
\end{align}

Denoting $\delta_t = g_t- \nabla f(z_t)$ and combining \eqref{eq:scgs-proof-1} and \eqref{eq:scgs-proof-2}, we obtain
\begin{align*}
	f(x_t)	 \leq & (1-\gamma_t) f(x_{t-1}) + \gamma_t f(x^*) + \gamma_t \inner{\delta_t, x^*-y_t}  \\
	&+ \frac{\beta_t\gamma_t}{2}(\norm{y_{t-1}-x^*}^2 -\norm{y_{t}-x^*}^2) +  \eta_t\gamma_t -\frac{\gamma_t}{2} (\beta_t - L\gamma_t) \norm{y_t - y_{t-1}}^2\\
	 = & (1-\gamma_t) f(x_{t-1}) + \gamma_t f(x^*)  + \frac{\beta_t\gamma_t}{2}(\norm{y_{t-1}-x^*}^2 -\norm{y_{t}-x^*}^2)+\eta_t\gamma_t\\
	 &+\gamma_t \inner{\delta_t, x^*-y_{t-1}} + \gamma_t \inner{\delta_t, y_{t-1}-y_t}  - \frac{\gamma_t}{2}(\beta_t - L\gamma_t)\norm{y_{t}-y_{t-1}}^2\\
	 \leq &(1-\gamma_t) f(x_{t-1}) + \gamma_t f(x^*)  + \frac{\beta_t\gamma_t}{2}(\norm{y_{t-1}-x^*}^2 -\norm{y_{t}-x^*}^2)+\eta_t\gamma_t\\
	 &+\gamma_t \inner{\delta_t, x^*-y_{t-1}} + \frac{\gamma_t\norm{\delta_t}^2}{2(\beta_t-L\gamma_{t})},
\end{align*}
where the last inequality comes from the fact that
\begin{equation*}
	\gamma_t \inner{ \delta_t, y_{t-1} - y_t }  \leq   \frac{\gamma_t}{2(\beta_t - L\gamma_t)} \norm{ \delta_t}^2 + \frac{\gamma_t(\beta_t - L\gamma_t)}{2}  \norm{y_t - y_{t-1}}^2.
\end{equation*}

Substracting $f(x^*)$ from both sides of the above inequality, denoting $\phi_t = f(x_t) - f(x^*)$, $\theta_t=\gamma_t$, and in the view of Lemma~\ref{gamma_recursive}, we obtain
\begin{equation}\label{eq:scgs-proof-basic-ineq}
	\phi_t \leq \Theta_t\left[\phi_0 +\sum_{k=1}^{t} \frac{B_k}{\Theta_k}\right],
\end{equation}
where
\begin{align*}
B_t &= \frac{\beta_t\gamma_t}{2}(\norm{y_{t-1}-x^*}^2 -\norm{y_{t}-x^*}^2)+\eta_t\gamma_t +\gamma_t \inner{\delta_t, x^*-y_{t-1}} + \frac{\gamma_t\norm{\delta_t}^2}{2(\beta_t-L\gamma_{t})}.
\end{align*}
Choosing $\gamma_t=\theta_t = \frac{3}{t+2}$, we can easily check that $\Theta_t = \frac{6}{t(t+1)(t+2)}$ due to \eqref{def_gamma}.
Moreover, letting $\beta_t = \frac{4L}{t+2}, \eta_t = \frac{LD^2}{t(t+1)}$, we have $\sum_{k=1}^{t} \frac{\eta_k\gamma_k}{\Theta_k}\leq \frac{tLD^2}{2}$ and

\begin{align*}
	& \sum_{k=1}^{t} \frac{\beta_k\gamma_k}{\Theta_k} (\norm{y_{t-1}-x^*}^2 -\norm{y_{t}-x^*}^2) \nonumber \\
	& \leq \frac{\beta_1\gamma_1}{\Theta_i} \norm{y_0 - x^*}^2 + \sum_{k=2}^{t} \bigg( \frac{\beta_k\gamma_k}{\Theta_k} - \frac{\beta_{k-1}\gamma_{k-1}}{\Theta_{k-1}} \bigg) \norm{y_{t-1}-x^*}^2\\
	&\leq \frac{\beta_1\gamma_1}{\Theta_i} D^2 + \sum_{k=2}^{t} \bigg( \frac{\beta_k\gamma_k}{\Theta_k} - \frac{\beta_{k-1}\gamma_{k-1}}{\Theta_{k-1}} \bigg) D^2 = \frac{\beta_t\gamma_t D^2}{\Theta_t} = \frac{2LD^2t(t+1)}{t+2},
\end{align*}
where the last inequality comes from the fact $\frac{\beta_k\gamma_k}{\Theta_k} > \frac{\beta_{k-1}\gamma_{k-1}}{\Theta_{k-1}}$.\\

We now prove part (a). Let $g_t = \tilde{\nabla}_t$. Taking expectation for both sides of \eqref{eq:scgs-proof-basic-ineq}, and noting that $	\E [\inner{\delta_t, x^*-y_{t-1}}]  = 0$ and
\begin{flalign*}
&&\E[\norm{\delta_t}^2|\mathcal{F}_{t-1}] & \leq \frac{2\rho L}{b_t} (f(z_t) - f(x^*)) \quad  \rhd \text{ by Assumption \ref{ass:WGC-variance}}\\
&& & \leq \frac{2\rho L}{b_t} \bigg( (1-\gamma_t) \phi_{t-1} + \gamma_t (f(y_{t-1})  - f(x^*) )  \bigg) \quad \rhd \text{$z_t = (1-\gamma_t)x_{t-1}  + \gamma_t y_{t-1} $}\\
&& & \leq \frac{2\rho L}{b_t} \bigg( (1-\gamma_t) \phi_{t-1} + \gamma_t(\|\nabla f(x^*) \|D + \frac{LD^2}{2})  \bigg) \quad \rhd \text{ by the smoothness}\\
&& & := \frac{2\rho L}{b_t} \bigg( (1-\gamma_t) \phi_{t-1} + \gamma_t \frac{K LD^2}{2}  \bigg),\quad \rhd  K = \frac{\| \nabla f(x^*) \|}{LD} +1
\end{flalign*}
we can obtain
\begin{equation*}
	\E [\phi_t] \leq \frac{6LD^2}{(t+2)^2} + \frac{3LD^2}{(t+1)(t+2)} + \frac{3}{t(t+1)(t+2)} \sum_{k=1}^{t}\frac{\rho k(k+1)\bigg( (k-1)\E [\phi_{k-1}]  + \frac{3KLD^2}{2}\bigg)}{b_k}
\end{equation*}

We now prove
\begin{equation}\label{eq:scgs-ind}
    	\E [\phi_t]  \leq \frac{6LD^2}{(t+2)^2} + \frac{(12+3K)LD^2}{(t+1)(t+2)}
\end{equation}
by induction. Set $b_k = \big\lceil 3\rho k(k+1)\big \rceil$. It is easy to check $\E[\phi_0] \leq \frac{KLD^2}{2} $ by the smoothness of $f$ which satisfies \eqref{eq:scgs-ind}. If \eqref{eq:scgs-ind} holds for all $k\leq t-1$, then with the above inequality we can obtain
\begin{align*}
	\E [\phi_t] &\leq \frac{6LD^2}{(t+2)^2} + \frac{(3+\frac{3K}{2})LD^2}{(t+1)(t+2)} + \frac{1}{t(t+1)(t+2)} \sum_{k=1}^{t}(k-1)\E [\phi_{k-1}]\\
	&\leq \frac{6LD^2}{(t+2)^2} + \frac{(3+\frac{3K}{2})LD^2}{(t+1)(t+2)} + \frac{1}{t(t+1)(t+2)} \sum_{k=1}^{t}\bigg( \frac{6LD^2(k-1)}{(k+1)^2} + \frac{(12+3K)LD^2(k-1)}{k(k+1)} \bigg)\\
	&\leq \frac{6LD^2}{(t+2)^2} + \frac{(3+\frac{3K}{2})LD^2}{(t+1)(t+2)} + \frac{(18+3K) LD^2}{t(t+1)(t+2)} \sum_{k=1}^{t} \frac{1}{k+1} \\
	&\leq \frac{6LD^2}{(t+2)^2} + \frac{(12+3K)LD^2}{(t+1)(t+2)},
\end{align*}
i.e., \eqref{eq:scgs-ind} holds for $k=t$. Therefore, to achieve an $\epsilon$-optimal point, the number of outer iterations $T$ can be bounded by $\mathcal{O}(1/\sqrt{\epsilon})$. Hence, the number of calls to the first order oracles can be bounded by
\begin{equation*}
	\sum_{t=1}^T b_t \leq 3\rho\sum_{t=1}^T t(t+1) = \rho T(T+1)(T+2) =\mathcal{O}(T^3).
\end{equation*}
Due to the fact that the inner iterations indeed solves a convex constrained optimization problem by the classical Frank-Wolfe method with the exact line search, one can show that the number of inner iterations $N_t$ performed at the $t$-th out iteration can be bounded by
\begin{equation*}
	N_t \leq \left\lceil \frac{6\beta_tD^2}{\eta_t} \right\rceil = \mathcal{O}(t).
\end{equation*}
Thus, the number of calls to the linear minimization oracle can be bounded by
\begin{equation*}
	\sum_{t=1}^T N_t \leq \mathcal{O}(T^2).
\end{equation*}

We now prove part (b). Let $g_t = \bar{G}_\nu^t$. Notice that $\bar{G}_\nu^t$ is a biased estimator of $\nabla f(z_t)$. We can obtain the following results by \eqref{eq:nestrov-bias}:
\begin{align*}
	\E[ \inner{\delta_t, x^* - y_{t-1}} ] &= \E[ \inner{\nabla f_{\nu}(z_t) - \nabla f(z_t), x^*- y_{t-1}}] + \E[ \inner{\bar{G}_\nu^t - \nabla f_{\nu}(z_t), x^*- y_{t-1}}]\\
	& =  \E[ \inner{\nabla f_{\nu}(z_t) - \nabla f(z_t), x^*- y_{t-1}}]\leq \frac{\nu LD(d+3)^{3/2}}{2}.
\end{align*}
Besides, we can obtain a similar bound for $\E[\norm{\delta_t}^2]$ by Lemma \ref{lem:zero_grad}.
\begin{align*}
	\E[\norm{\delta_t}^2|\mathcal{F}_{t-1}] &\leq  \frac{ 4\rho L(d+4)(f(z_{t}) - f(x^*)) }{b_t} + \nu^2 L^2 (d+6)^3\\
	&\leq  \frac{ 4\rho L(d+4)\big( (1-\gamma_t) \phi_{t-1} + \frac{LD^2\gamma_t}{2}  \big) }{b_t} + \nu^2 L^2 (d+6)^3.
\end{align*}
where the last inequality is slightly different from the one for the first-order setting due to  $\| \nabla f(x^*) \| = 0$ for convex cases under the moment-based WGC.

By \eqref{eq:scgs-proof-basic-ineq}, we have the following simplified inequality:
\begin{align*}
	\E[\phi_t] \leq & \frac{6LD^2}{(t+2)^2} + \frac{3LD^2}{(t+1)(t+2)} + \frac{\nu LD(d+3)^{3/2}}{2} + \frac{3\nu^2L(d+6)^3}{2} \\&~~+ \frac{6}{t(t+1)(t+2)} \sum_{k=1}^{t}\frac{\rho(d+4) k(k+1)\bigg( (k-1)\E [\phi_{k-1}]  + \frac{3LD^2}{2}\bigg)}{b_k}.
\end{align*}
Set $b_k = \lceil 6\rho k(k+1)(d+4) \rceil, \nu =\frac{D}{(T+2)^2(d+6)^{3/2}}\leq \frac{D}{(t+2)^2(d+6)^{3/2}}$. Then we have
\begin{equation*}
	\E[\phi_t] \leq \frac{8LD^2}{(t+2)^2} + \frac{12LD^2}{(t+1)(t+2)} + \frac{1}{t(t+1)(t+2)} \sum_{k=1}^{t} (k-1)\E [\phi_{k-1}].
\end{equation*}
Similar to the proof for part (a), we can finish the proof by induction and obtain the bounds for complexity.
\end{proof}

\iffalse
\section{Proof of Theorem~\ref{thm:sfw-nonconvex-wgc}}

\begin{proof}[Proof for Theorem \ref{thm:sfw-nonconvex-wgc}] For convenience, let $g_t$ be the gradient estimator at $t$ step. Thus, $g_t = \tilde{\grad}_t$ for the first order method while in the zeroth order setting $g_t = \bar{G}_{\nu}^t$. Denote
$$\bar{d}_t = \argmin_{d \in \Omega} \langle \nabla f(x_{t-1}),d \rangle, \quad \mathcal{G}_t =   \langle \nabla f(x_{t-1}), x_{t-1}- \bar{d}_t\rangle. $$

Recalling the definition of $d_t$ in Algorithm~\ref{alg:NCSFW}, we have $\langle d_t,g_t\rangle \leq \langle u,g_t\rangle$, for all $u\in \Omega$. Setting, $u=\bar{d}_t$, we have $\langle g_t, \bar{d}_t - d_t \rangle \geq 0$. Now, we have
\begin{align*}
    f(x_t) &\leq f(x_{t-1}) +  \inner{\grad f(x_{t-1}), x_t-x_{t-1}} + \frac{L}{2} \norm{x_t - x_{t-1}}^2 \\
    &= f(x_{t-1}) +  \gamma_t\inner{\grad f(x_{t-1}), d_t-x_{t-1}} + \frac{L\gamma_t^2}{2} \norm{d_t- x_{t-1}}^2 \\
     &= f(x_{t-1}) -\gamma_t \mathcal{G}_t + \gamma_t\inner{\grad f(x_{t-1}), d_t-\bar{d}_{t}} + \frac{L\gamma_t^2}{2} \norm{d_t- x_{t-1}}^2 \\
          &\leq f(x_{t-1}) -\gamma_t \mathcal{G}_t  + \gamma_t\inner{\grad f(x_{t-1}) , d_t-\bar{d}_{t}} + \langle g_t, \bar{d}_t-d_t\rangle+ \frac{L\gamma_t^2}{2} \norm{d_t- x_{t-1}}^2 \\
                    &\leq f(x_{t-1}) -\gamma_t \mathcal{G}_t  + \gamma_t\inner{\grad f(x_{t-1})-g_t,d_t-\bar{d}_{t}}+ \frac{L\gamma_t^2 D^2}{2} \numberthis \label{eq:nonconvex-basic-ineq}
\end{align*}

Considering the term $\gamma_t\inner{\grad f(x_{t-1})-g_t,d_t-\bar{d}_{t}}$ and applying the Young's inequality, we can obtain that for any $\beta\geq 0$
\begin{align*}
\gamma_t\inner{\grad f(x_{t-1})-g_t,d_t-\bar{d}_{t}} &\leq \frac{1}{2\beta}\| \grad f(x_{t-1}) - g_t \|^2 + \frac{\beta\gamma_t^2}{2} \|d_t -\bar{d}_t\|^2 \\
& \leq \frac{1}{2\beta}\| \grad f(x_{t-1}) - g_t \|^2 + \frac{\beta\gamma_t^2 D^2}{2}.
\end{align*}

We now prove part (a). Let $g_t = \tilde{\nabla}_t$. By Assumption~\ref{ass:CGC-variance}, taking expectation with respect to $\xi_1, \dots, \xi_{t}$, we have
$$
\E\| \grad f(x_{t-1}) - g_t \|^2 \leq  \frac{2\rho L}{b_t} \E[\mathcal{G}_t].
$$
Hence, setting $\beta = \rho L$ and by \eqref{eq:nonconvex-basic-ineq}, we have
\begin{align*}
 \bigg( \gamma_t -  \frac{1}{b_t} \bigg) \E[\mathcal{G}_t] \leq \E[f(x_{t-1}) - f(x_t)] + \frac{(\rho +1)LD^2\gamma_t^2}{2}
\end{align*}

Setting $ b_t = \lceil\frac{2}{\gamma_t}\rceil$ and taking a telescoping sum of the above inequalities from 1 to $T$, we have
\begin{align*}
\sum_{t=1}^{T} \gamma_t \E[\mathcal{G}_t] &\leq  2\E[f(x_0) - f(x_T)] + (\rho +1)LD^2\sum_{t=1}^{T}\gamma_t^2\\
&\leq 2(f(x_0) - f(x^*)) + (\rho +1)LD^2 \sum_{t=1}^T\gamma_t^2
\end{align*}
Let $\gamma_t = \frac{1}{\sqrt{T}}$. Thus, according to Algorithm~\ref{alg:NCSFW}, we have
\begin{equation}
	\E[\mathcal{G}(x_R)] = \E[\mathcal{G}_{R+1})] = \frac{\sum_{t=1}^{T}\gamma_t \E[\mathcal{G}_t]}{\sum_{t=1}^{T}\gamma_t}  \leq \frac{2(f(x_0) - f(x^*)) + (\rho+1)LD^2 }{\sqrt{T}}
\end{equation}

Hence, to attain an $\epsilon$-stationary point, the total number of interations $T$ can be bounded by $\mathcal{O}(1/\epsilon^2).$ Hence, the number of the gradient calls $\sum_{t=1}^T b_t$ can be bounded by $T^{1.5} = \mathcal{O}(1/\epsilon^3)$, and the number of \blue{linear minimization problems} $T$ immediately follows from this observation.\\

We then prove part (b). Let $g_t = \bar{G}_\nu^t$. Then, by Lemma \ref{lem:zero_grad}, we can obtain the following bound for the mean squared error:
\begin{align*}
	\E \|\grad f(x_{t-1}) - g_t \|^2  &= \E \| \bar{G}_\nu^t - \grad f_\nu(x_{t-1}) ]\|^2 + \| \grad f_{\nu}(x_{t-1}) - \grad f(x_{t-1}) \|^2\\
	&\leq \frac{1}{b_t} \E_{u, \xi} \norm {G_{t,j}}^2 + \frac{\nu^2L^2(d+3)^{3}}{4}\\
	&\leq \frac{2(d+4)}{b_t}\E_{\xi} \norm{\grad F(x_{t-1}, \xi_{t,j})}^2 + \frac{\nu^2 L^2 (d+6)^3}{2b_t} + \frac{\nu^2L^2(d+3)^{3}}{4}\\
	&\leq  \frac{ 4\rho L (d+4)\mathcal{G}_t }{b_t} + \nu^2 L^2 (d+6)^3.
\end{align*}

Setting $\beta = \rho L, b_t = \lceil 4(d+4)/\gamma_t \rceil$ and taking expectation for both sides of\eqref{eq:nonconvex-basic-ineq} with respect to $\xi_1, \dots, \xi_t$ by , we can obtain
\begin{align*}
 \gamma_t \E[\mathcal{G}_t] &\leq  2\E[f(x_{t-1}) - f(x_t)] + \rho^{-1}\nu^2 L (d+6)^3 + (\rho+1)LD^2\gamma_t^2\\
\end{align*}

Taking a telescoping sum of the above inequalities from 1 to $T$, we have
\begin{align*}
\sum_{t=1}^{T}\gamma_t \E[\mathcal{G}_t] &\leq  2\E[f(x_0) - f(x_T)] + T\rho^{-1}\nu^2 L (d+6)^3 + (\rho+1)LD^2\sum_{t=1}^{T}\gamma_t^2\\
&\leq 2(f(x_0) - f(x^*)) + T\rho^{-1}\nu^2 L (d+6)^3 + (\rho+1)LD^2\sum_{t=1}^{T}\gamma_t^2.
\end{align*}

Let $\gamma_t = \frac{1}{\sqrt{T}}, \nu = \frac{D}{\sqrt{T(d+6)^{3}}}$. Thus, according to Algorithm~\ref{alg:NCSFW}, we have
\begin{equation}
\E[\mathcal{G}(x_R)] = \E[\mathcal{G}_{R+1})] \leq \frac{2(f(x_0) - f(x^*)) + (\rho+\rho^{-1}+1)LD^2}{\sqrt{T}}.
\end{equation}

The above inequality implies, to attain an $\epsilon$-stationary point, the total number of interations $T$ can be bounded by $\mathcal{O}(1/\epsilon^2).$ Hence, the number of the zeroth-order oracle calls $\sum_{t=1}^T b_t$ can be bounded by $4(d
+4)T^{1.5} = \mathcal{O}(d/\epsilon^3)$.

\end{proof}

\fi
\iffalse

\section{Proof of Proposition~\ref{thm:dp-sfw}}
\begin{proof}[Proof of Proposition~\ref{thm:dp-sfw}]
By Assumption~\ref{ass:dp}, we can see that $\Delta_2(g_t) = L\Gamma/b_t$. Denote $\phi_t = f(x_t) - f(x^*)$. Following the same argument for SFW, we can obtain
\begin{equation*}
    \E[\phi_t] \leq (1-\gamma_t) \E[\phi_{t-1}] + \frac{\gamma_t}{2\beta} \E [\norm{\grad f(x_{t-1}) - \tilde{g}_t}^2 ] + \frac{D^2 \gamma_t (L\gamma_t + \beta)}{2}.
\end{equation*}
For the DP-variant with $\epsilon = \mathcal{O}(1), \delta_t = o(1/b_t)$, we can see that
\begin{align*}
    \E [\norm{\grad f(x_{t-1}) - \tilde{g}_t}^2 ] \leq \frac{\E \| \nabla F(x_{t-1},\xi_j) -\nabla f(x_{t-1}) \|^2}{b_t} + 2d\log(1.25/\delta_t) \frac{L^2\Gamma^2}{\epsilon^2 b_t^2}
\end{align*}
Then, without the variance-based WGC,
\begin{align*}
    \E [\norm{\grad f(x_{t-1}) - \tilde{g}_t}^2 ] \leq \frac{\sigma^2}{b_t} + 2d\log(1.25/\delta_t) \frac{L^2\Gamma^2}{\epsilon^2 b_t^2}\lesssim \frac{d}{b_t}.
\end{align*}
One can show that with $b_t = \mathcal{O}(t^2)$, $ \E [\phi_t ] \leq \mathcal{O}(d/t)$, which is equivalent to the vanilla SFW.

However, with the variance-based WGC ,
\begin{align*}
    \E [\norm{\grad f(x_{t-1}) - \tilde{g}_t}^2 ] \leq \frac{2\rho L \phi_{t-1}}{b_t} + 2d\log(1.25/\delta_t) \frac{L^2\Gamma^2}{\epsilon^2 b_t^2}.
\end{align*}
Let $\gamma_t = \frac{4}{t+3}, \beta = \rho L \gamma_t = \frac{4\rho L}{t+3}> 0, b_t = \lceil(t+3)/2\rceil$, then
\begin{align*}
     \E[\phi_t] &\leq\left(1-\frac{2}{t+3}\right) \E [\phi_{t-1}] + \frac{8d\log(1.25/\delta_t) L\Gamma^2}{\rho \epsilon_t^2 (t+3)^2}+  \frac{8(\rho+1)LD^2}{(t+3)^2}.\\
     &=\left(1-\frac{2}{t+3}\right) \phi_{t-1} + \frac{8d\log(1.25/\delta_t) L\Gamma^2/\rho\epsilon_t^2 + 8(\rho+1)LD^2}{(t+3)^2}
\end{align*}
One can show by induction that $\E [\phi_t] \leq \mathcal{O} (\frac{d\log(1/\delta_t)}{t})$
\end{proof}
\fi

\section{Zeroth-order SGD under Growth Conditions}\label{sec:sgdproofs}

In this section, we highlight that one can extend the results in \cite{vaswani2019fast} only assuming access to stochastic zeroth-order oracle with corresponding variance-based growth conditions. Notice that both SGC and WGC are defined in the format of the relative shrinkage of $\E \|\nabla F(x,\xi) \|^2$. However, in the unconstrained setting, the corresponding variance-based versions are equivalent to the moment-based growth conditions (see Proposition~\ref{prop:WGC} for WGC; for SGC, note that $\E \| \nabla F(x, \xi) - \nabla f(x)  \|^2 = \E \| \nabla F(x, \xi) \|^2 - \|  \nabla f(x) \|^2 =(\rho-1)\| \nabla f(x) \|^2$).

We present the following result for the zeroth-order setting which directly follows the proofs in \cite{vaswani2019fast}. We highlight that it is the zeroth-order version of Theorem 3 in \cite{vaswani2019fast}. Similar results for other setups considered in~\cite{vaswani2019fast} can also be obtained for the zeroth-order setting.
\begin{algorithm}[h]
\caption{Non-convex Zeroth-order SGD (ZO-SGD)}
\begin{algorithmic}
 \STATE \textbf{Input:} $x_0\in \Omega$, number of iterations $T$, $\eta$
    \FOR{$t = 1, 2, \dots, T$}
        \STATE  Randomly pick $\xi_{t}$ and compute
        $$x_{t} = x_{t-1} - \eta \frac{F(x_{t-1} + \nu u_t, \xi_t ) - F(x_{t-1}, \xi_t)}{\nu} u_{t} := x_{t-1} - \eta G_{t}.  $$
        where $u_{t}$ is generated from $\normal(0, \mathbf{I}_d)$.
    \ENDFOR
    \STATE \textbf{Output:} $x_R$ where $R$ is uniformly distributed over ${0, \dots , T-1}$
\end{algorithmic}
\label{alg:ZO-SGD}
\end{algorithm}

\begin{theorem}
Consider solving the non-convex unconstrained $L$-smooth problem by Algorithm~\ref{alg:ZO-SGD} with some appropriate constant step size $\eta$, if $f$ satistifies SGC with constant $\rho$, then
\begin{equation*}
    \E \| \grad f(x_R) \|^2  \leq \mathcal{O}\left(\frac{1}{T}\right)
\end{equation*}
\end{theorem}
\begin{proof-idea}
The zeroth-order SGD update is given by $$x_{t} = x_{t-1} - \eta \frac{F(x_{t-1} + \nu u_t, \xi_t ) - F(x_{t-1}, \xi_t)}{\nu} u_{t} := x_{t-1} - \eta G_{t}.  $$

By the smoothness of $f$, we have
\begin{align*}
	f(x_{t}) - f(x_{t-1}) &\leq \langle \nabla f(x_{t-1}, x_t - x_{t-1}) + \frac{L}{2}\| x_t -x_{t-1} \|^2\\
	&= -\eta \langle \nabla f(x_{t-1}) , G_t \rangle + \frac{L\eta^2}{2} \| G_t \|^2
\end{align*}
 Consider the term $\langle \nabla f(x_{t-1}) , G_t \rangle$. Taking expectation with respect to $\xi_t,u_t$, we have
\begin{align*}
	\E [\langle \nabla f(x_{t-1}) , G_t \rangle ]  &= \langle \nabla f(x_{t-1}), \nabla f_\nu (x_{t-1}) \rangle\\
	& = \langle \nabla f(x_{t-1}), \nabla f(x_{t-1}) + \nabla f_\nu (x_{t-1}) - \nabla f(x_{t-1}) \rangle\\
	&\geq \| \nabla f(x_{t-1}) \|^2  - \frac{\nu L(d+3)^{3/2}}{2}\| \nabla f(x_{t-1}) \|
\end{align*}
 Consider the term $\| G_t \|^2$. Taking expectation with respect to $\xi_t,u_t$, we have
\begin{align*}
	\E \| G_t \|^2 &\leq \frac{\nu^2}{2}L^2 (d+6)^3 + 2(d+4) \E \| \nabla F(x_{t-1}, \xi_t) \|^2\\
	&\leq \frac{\nu^2}{2}L^2 (d+6)^3 + 2\rho (d+4) \| \nabla f(x_{t-1}) \|^2
\end{align*}
Then, by the above inequalities, we can obtain
\begin{align*}
	&\E [ f(x_t) - f(x_{t-1}) ] \\
	&\leq -\eta \| \nabla f(x_{t-1}) \|^2 + \eta\frac{\nu L(d+3)^{3/2}}{2}\| \nabla f(x_{t-1}) \| +\eta^2 L\rho(d+4) \| \nabla f(x_{t-1}) \|^2 + \eta^2\frac{\nu^2}{4}L^3(d+6)^2\\
	&\leq  -\eta \| \nabla f(x_{t-1}) \|^2 + \eta^2L(d+3) \| \nabla f(x_{t-1}) \|^2 + \frac{\nu^2 L(d+3)^2}{16}  \\ &\quad\quad +\eta^2 L\rho(d+4) \| \nabla f(x_{t-1}) \|^2 + \eta^2\frac{\nu^2}{4}L^3(d+6)^2\\
	&\leq -\eta \| \nabla f(x_{t-1}) \|^2 + \eta^2L(\rho+1)(d+4) \| \nabla f(x_{t-1}) \|^2 + \eta^2\frac{\nu^2}{4}L^3(d+6)^2 + \frac{\nu^2 L(d+3)^2}{16}.
\end{align*}
If $\eta = \frac{1}{2L(\rho+1)(d+4)}$, then we have
\begin{align*}
	\E [ f(x_t) - f(x_{t-1}) ] \leq -\frac{\eta}{2}  \| \nabla f(x_{t-1}) \|^2 + \eta^2\frac{\nu^2}{4}L^3(d+6)^2 + \frac{\nu^2 L(d+3)^2}{16}\\
	\Rightarrow  \| \nabla f(x_{t-1}) \|^2 \leq \frac{2}{\eta}\E [ f(x_{t-1}) - f(x_{t}) ] + \eta\frac{\nu^2}{2}L^3(d+6)^2 + \frac{\nu^2 L(d+3)^2}{8\eta}
\end{align*}
Setting $\nu = \mathcal{O}(1/\sqrt{dT})$ and taking a telescoping sum of the above inequality, we can get the same $\mathcal{O}(1/T)$ rate for the non-convex setting.
\end{proof-idea}
 In the above proof, we did not pay careful attention to the exact constants of the tuning parameter, as our main point is to simply highlight it is possible to obtain a zeroth-order version of the results in~\cite{vaswani2019fast} under variance-based growth conditions and the logic of the proof is the same as~\cite{vaswani2019fast}.


TITLE: Who first defined open sets in terms of neighborhoods?
QUESTION [7 upvotes]: One way to define a topology for a set (of "points") X is to first give a suitable definition of a neighborhood of $x$, for any point $x \in X$, and then to define an open set as any subset of $X$ that is a neighborhood of all of its elements.  A topology for $X$ is then defined as the family of all open subsets of $X$.
I would like to know who first proposed this particular approach to defining a topology.
(Note that another approach first defines open sets, and then defines neighborhoods in term of open sets.  Yet another approach takes the closure of a set as the fundamental definition.  Etc.)
EDIT: The motivation behind this question can be found in this other question.  In that question I give a verbatim rendition of a set of axioms defining neighborhoods and then defining open sets in terms of neighborhoods.  I argue that these axioms, as stated, are faulty.  Later (in my answer to the question) I show what I believe is the genesis of the error.  The problem lies in the subtle difference between the following two alternative versions of one of the axioms:
(B$3$) for each $x$, the set of neighborhoods of $x$ is closed under non-infinite intersections;
(B$3^{\prime}$) if $U_1, \dots, U_n$ are neighborhoods of $x$, then $U_1 \cap \dots \cap U_n$ is a neighborhood of $x$;
(Of course, one typically writes finite instead of the awkward non-infinite, but I've used the latter in (B$3$) to bring out the fact that the axiom applies to the empty intersection as well.  IOW, the axiom implies that, for each $x \in X$, the entire set $X$ is a neighborhood of $x$.)
In fact I've come across even more emphatic versions of (B$3^\prime$):
(B$3^{\prime\prime}$) if $U_1$ and $U_2$ are neighborhoods of $x$, then $U_1 \cap U_2$ is a neighborhood of $x$;
The problem with (B$3^\prime$) and (B$3^{\prime\prime}$) is that they fail to rule out the case in which some $x \in X$ has no neighborhoods at all, which in turn will imply that the entire space $X$ is not open.
My interest in this question is that I have found at least three separate mentions in the literature of the faulty set of axioms, one as recent as 1997.  It appears that this is a case of an error that has been propagated for decades, and I'm curious about its origin.  In fact, it's not hard to imagine a sequence of rewordings $\text{B}3 \to \text{B}3^\prime \to \text{B}3^{\prime\prime}$.

REPLY [10 votes]: Felix Hausdorff wrote 1914 in his book "Grundzüge der Mengenlehre":

(A) Jedem Punkt entspricht mindestens eine Umgebung $U_x$; jede Umgebung $U_x$ enthält den Punkt $x$.
  (B) Sind $U_x$, $V_x$ zwei Umgebungen desselben Punktes $x$, so gibt es eine Umgebung $W_x$, die Teilmenge von beiden ist ($W_x \subseteqq \mathfrak D(U_x, V_x)$).
  (C) Liegt der Punkt $y$ in $U_x$, so gibt es eine Umgebung $U_y$, die Teilmenge von $U_x$ ist ($U_y \subseteqq U_x$).
  (D) Für zwei verschiedene Punkte $x,y$ gibt es zwei Umgebungen $U_x, U_y$ ohne gemeinsamen Punkt ($\mathfrak D(U_x, U_y) = 0$).

My translation:

(A) Each point has at least one neighbourhood $U_x$; each neighbourhood $U_x$ contains $x$.
  (B) If $U_x$, $V_x$ are two neighbourhoods of the same point $x$, then there is a neighbourhood $W_x$, which is a subset of both ($W_x \subseteqq \mathfrak D(U_x, V_x)$).
  (C) If $y$ is a point of $U_x$, then there is a neighbourhood $U_y$, which is a subset of $U_x$ ($U_y \subseteqq U_x$).
  (D) Each two different points $x,y$ have neighbourhoods $U_x$, $U_y$ which do not have a common point ($\mathfrak D(U_x, U_y) = 0$).

As far as I know this is one the earliest definitions of the concept "topological space" (to be exact, of a Hausdorff space due to axiom (D)) and the first which uses neighbourhoods (note: $\mathfrak D$ denotes the intersection herein, it is the first letter of the german "Durchschnitt").


TITLE: Lagrange's Multiplier for $f(x,y,z) = (xyz)^2$
QUESTION [1 upvotes]: Given a function:
$$f(x,y,z) = (xyz)^2$$
And the set: $$S = \{(x,y,z) : x^2 + y^2 + z^2  = a^2\} $$
Does $f$ have a maxima on $S$?
(Is this argument correct? : Yes, because f has a maxima and minima in S if S is compact and f is continuous. But here S is compact so we have a maxima)
Also, how do I tell if a function has maxima or minima on a set if the set is not compact?
I tried using the lagrange multiplier.
$f_x = 2xy^2z^2$, $f_y = 2yx^2z^2$,  $f_z = 2zx^2y^2$, $f_\lambda = x^2 + y^2 + z^2 - a^2$
$$f_x + \lambda g_x = 0$$
$$f_y + \lambda g_y = 0$$
$$f_z + \lambda g_z = 0$$
$$f_\lambda = 0$$
However on solving this system of equations using substitution, I am unable to find a solution for (x,y,z). I did find one point though (0,0,0), for $a = 0$,  Can I set $a$ to be $0$?
$$2xy^2z^2 = \lambda2x$$
$$2yx^2z^2 = \lambda2y$$
$$2zx^2y^2 = \lambda2z$$
So suppose $x = 0$ and $\lambda \not = 0$, we have $\lambda2y = 0$, so $y = 0$, similarly $z = 0$, $(0,0,0)$ satisfies $f_\lambda = 0$ for $a = 0$, so this is one point.
However, evaluating for other points, I am unable to simplify.
For $x \not = 0$, we have: $y^2z^2 = \lambda$
But how do I proceed from now?
Can I say by symmetry, if any one of $x$, $y$ or $z$ is $0$ then they all have to be $0$?
If so, then we have all non zero :
$$x^2z^2 = x^2y^2 = y^2z^2$$
which means $$ x^2 = y^2 = z^2$$
And then substituting this into constraint, we get 6 points of the form
$$( \pm\ a/\sqrt3, \pm\ a/\sqrt3, \pm\ a/\sqrt3)$$
Is this correct?

REPLY [0 votes]: Define : $\mathcal{L}(x,y,z,\lambda) = (xyz)^2 - \lambda\cdot(x^2 + y^2 + z^2 - a^2)$ for any $\lambda \in \mathbb{R}$ , and for any $x, y, z \in \mathbb{R}$ .
So, $~\mathcal{L}_x = 2xy^2z^2 - 2\lambda x~$ , $~\mathcal{L}_x = 2x^2yz^2 - 2\lambda y~$ , and $~\mathcal{L}_x = 2x^2y^2z - 2\lambda z~$ . Also, we have : $~\mathcal{L}_\lambda = a^2 - (x^2 + y^2 + z^2)~$ .
Equating these to $0$ , we get : $\lambda = x^2y^2 = y^2z^2 = z^2x^2~$ , and $~~a^2 = x^2 + y^2 + z^2$ .
Now, if any of $x, y, z$ is $0$ , then $f$ won't be maximized for sure, in fact it'll get minimized then. So , multiplying the first $3$ constraints by $z^2, x^2 , y^2$ respectively , we get $\lambda x^2 = \lambda y^2 = \lambda z^2$ , which implies that $f$ is maximized when $x^2 = y^2 = z^2 = k~$ (Say) .
Thus, by Lagrange Multiplier Theorem, using the 4th constraint, we get that $f$ is maximized when $a^2 = x^2 + y^2 + z^2 = 3k$ , i.e. $~x^2 = y^2 = z^2 = \frac{a^2}{3}$ .
Therefore, $f$ is maximized when $~(x,y,z) = \left(\pm\dfrac{| a |}{3} , \pm\dfrac{| a |}{3} , \pm\dfrac{| a |}{3} \right)$ , and the maximum value of will be $\dfrac{a^6}{27}$ .

In fact, you don't need a strong result like Lagrange Multiplier in order to solve this problem. Observe that by simple AM-GM Inequality, we have : $$(xyz)^2 = x^2\cdot y^2 \cdot z^2 \leqslant \left[\dfrac{x^2 + y^2 + z^2}{3}\right]^3 = \left(\dfrac{a^2}{3}\right)^3 = \dfrac{a^6}{27}$$ and the maximum is attained when $x^2 = y^2 = z^2 = \dfrac{a^2}{3}$ , which is certainly same as the result produced using Lagrange Multiplier. Hope it helps.