\begin{document}
\maketitle


\begin{abstract}
We analyze stochastic conditional gradient methods for constrained optimization problems arising in over-parametrized machine learning. We show that one could leverage the interpolation-like conditions satisfied by such models to obtain improved oracle complexities. Specifically, when the objective function is convex, we show that the conditional gradient method requires $\mathcal{O}(\epsilon^{-2})$ calls to the stochastic gradient oracle to find an $\epsilon$-optimal solution. Furthermore, by including a gradient sliding step, we show that the number of calls reduces to $\mathcal{O}(\epsilon^{-1.5})$.
\end{abstract}

\keywords{Stochastic Conditional Gradient, Oracle Complexity, Overparametrization, Zeroth-order Optimization.}


\input{intro}
\input{SectionGC}
\section{Improved Complexities for Stochastic Conditional Gradient Methods}
We now provide improved complexities for stochastic conditional gradient methods under the interpolation-like assumption in Section~\ref{sec:assumptions}. For convenience, we first introduce the following mini-batch stochastic gradients with first-order and zeroth-order oracle access: at $t$-th iteration, we uniformly pick i.i.d. samples $\{\xi_{t,1}, \dots, \xi_{t, b_t}\}$ and  estimate the gradient by
\begin{equation*}
	\Tilde{\nabla}_t := \frac{1}{b_t} \sum_{i=1}^{b_t} \nabla F(x_{t-1}, \xi_{t,i}), \quad
	\bar{G}_{\nu}^{t} := \frac{1}{b_t}  \sum_{j=1}^{b_t} \frac{F(x_{t-1} + \nu u_{t,j}, \xi_{t,j}) -  F(x_{t-1}, \xi_{t,j}) }{\nu} u_{t,j}
\end{equation*}
where $u_{t,1},\dots, u_{t.b_t}$ are i.i.d. samples from $\normal(0, \mathbf{I}_d)$.

\input{SectionSFW}
\input{SectionSliding}
\input{experiments}
\input{discussion}

\section*{Acknowledgements}
TX and KB were partially supported by a seed grant from the Center for Data Science and Artificial Intelligence Research,  UC Davis and NSF TRIPODS Grant-1934568.


\bibliography{bibtex}
\bibliographystyle{abbrv}


\clearpage

 { \hspace{1.72in} \bf {\normalsize SUPPLEMENTARY DOCUMENT}}
 
 


\appendix
\input{proof_ORL}

\end{document}
{"config": "arxiv", "file": "2006.08167/main.tex"}