\subsection{Stochastic Frank-Wolfe}

In this section, we studied the oracle complexity of the vanilla stochastic Frank-Wolfe algorithm under the weak interpolation-like conditions in Assumption~\ref{ass:WGC-variance} and~\ref{ass:WGC-moment}.

\begin{algorithm}[tb]
\caption{Stochastic Frank-Wolfe}
\begin{algorithmic}
	\STATE \textbf{Input:} $x_0\in \Omega$, number of iterations $T$, $\gamma_t \in [0,1]$, minibatch size $b_t$
    \FOR{$t = 1, 2, \dots, T$}
        
        \STATE Compute the gradient $g_t$ as follows:
        \begin{itemize}[topsep=1pt, partopsep=1pt, itemsep=1pt,parsep=1pt]
        \item[]  Set $g_t = \Tilde{\nabla}_t$ (for the first-order setting).
        \item[] Set $g_t = \bar{G}_{\nu}^{t}$ (for the zeroth-order setting).
        \end{itemize}
        \STATE Compute $d_t = \argmin_{d\in \Omega}  \inner{d, g_t}$
        \STATE $x_{t} = x_{t-1} + \gamma_t(d_t-x_{t-1})$
    \ENDFOR
    \STATE \textbf{Output:} $x_T$
\end{algorithmic}
\label{alg:SFWFandZ}
\end{algorithm}

\begin{theorem}\label{thm:sfw-convex-wgc}
Consider solving problem~\eqref{eq:sopt}, by Algorithm~\ref{alg:SFWFandZ}, under Assumption~\ref{ass:constrained} with $f$ being convex.
\begin{itemize}[leftmargin=0.2cm,align=left, topsep=1pt, partopsep=1pt, itemsep=1pt,parsep=1pt]
	\item[(a)] Assuming access to stochastic first-order oracle, under Assumption~\ref{ass:WGC-variance},
setting
\begin{equation*}
	\gamma_t = \frac{4}{t+3},\quad b_t = \lceil (t+3)/2 \rceil,
\end{equation*}
we have the following convergence rate:
\begin{equation*}
     \E[f(x_t) - f(x^*)] \leq \frac{2(f(x_0) - f(x^*))+8(\rho+1) LD^2}{t+3}.
\end{equation*}
Hence, the total number of calls to the stochastic first-order oracle and linear minimization oracle required to be
solved to find an $\epsilon$-optimal point of problem \eqref{eq:sopt} are, respectively, bounded by 
\begin{equation*}
	\mathcal{O}\left(\epsilon^{-2}\right),\quad \mathcal{O}\left(\epsilon^{-1}\right).
\end{equation*} 
\item[(b)]  Assuming access to stochastic zeroth-order oracle, under Assumptions~\ref{ass:WGC-moment}~and~\ref{ass:smooth-F}, setting 
\begin{align*}
	\gamma_t = \frac{4}{t+3},\quad  b_t = (t+3)(d+4),\quad  \nu = \frac{ D} {(T+3)(d+6)^{3/2}}
\end{align*}
we have
\begin{equation*}
	\E[f(x_t) - f(x^*)] \leq \frac{2(f(x_0) - f(x^*))+8(\rho + \rho^{-1}+1) LD^2}{t+3}.
\end{equation*}
Hence, the total number of calls to the stochastic zeroth-order oracle and linear minimization oracle required to be
solved to find an $\epsilon$-optimal point of problem \eqref{eq:sopt} are, respectively, bounded by
\begin{equation*}
	\mathcal{O}\left(d\epsilon^{-2}\right), \quad \mathcal{O}\left(\epsilon^{-1}\right).
\end{equation*}
\end{itemize}
\end{theorem}

The above oracle complexities in the first-order setting, match the results obtained by~\cite{yurtsever2019conditional, zhang2019one}. However, the above works require double-loop based variance reduction techniques which in turn require the stronger mean-square gradient-Lipschitz assumption. Furthermore, the use of the variance reduction technique results in the increased wall-clock running time of the algorithm. Our result here is applicable to the vanilla version of the stochastic conditional gradient method, as long as the problem satisfies the interpolation-like conditions observed in modern machine learning problems.
{"config": "arxiv", "file": "2006.08167/SectionSFW.tex"}