\section{Introduction}
Consider the following constrained stochastic optimization problem: 
\begin{equation}\label{eq:sopt}
    \underset{x \in \Omega}{\min}\quad \left\{f(x):= \E_\xi \left[ F(x, \xi)\right] \right\},
\end{equation}
where $f: \mathbb{R}^d \to \mathbb{R}$ and $\Omega \subset \mathbb{R}^d$ is a closed and convex set and $\xi$ is a random vector characterizing the stochasticity in the problem. In a machine learning setup, the function $F$ could be interpreted as the loss function associated with a sample $\xi$ and the function $f$ could represent the risk, which is defined as the expected loss. Such constrained stochastic optimization problems arise frequently in statistical machine learning applications. The conditional gradient algorithm,  also called as the Frank-Wolfe algorithm, is an efficient method for solving constrained optimization problems of the form in~\eqref{eq:sopt} due to their projection-free nature~\cite{jaggi2013revisiting, harchaoui2015conditional, freund2017extended, lan2017conditional, berrada2018deep, ravi2018constrained}. In each step of the conditional gradient method,  it is only required to minimize a linear objective over the set $\Omega$. This operation could be implemented efficiently for a variety of sets arising in statistical machine learning,  compared to the operation of projecting onto the set $\Omega$, which is required for example by the projected gradient method. Hence, the conditional gradient method has regained popularity in the last decade in the optimization and machine learning community.


There has been extensive work in the past decade on analyzing the stochastic conditional gradient algorithm for optimization problems of the form in~\eqref{eq:sopt}; see for example~\cite{garber2013linearly, hazan2016variance, lan2016conditional,reddi2016stochastic, ghadimi2019conditional}.  However, existing works do not take into account certain favorable structures that are naturally available in modern over-parametrized machine learning problems. \textcolor{black}{Specifically, it has been noted that modern machine learning models predict well on unseen data, despite fitting the training data perfectly~\cite{zhang2016understanding, huang2017densely, liang2018just, ma2018power, montanari2019generalization, hastie2019surprises}}. Examples include logistic regression or support vector machine with squared-hinge loss that are trained with linearly separable data~\cite{vaswani2019fast,vaswani2019painless,meng2019fast} and deep neural networks~\cite{vaswani2019fast,bassily2018exponential}. From an optimization point of view, for the problem in~\eqref{eq:sopt} with $\Omega\equiv\mathbb{R}^d$, the above interpolation condition means that at the optimal point, the gradient is not only zero (or close to zero) with respect to the risk function $f$ but is also almost surely equal to zero for the random loss function $F$. Such a scenario helps to reduce the stochasticity in the gradient estimation process which in turn results in improved complexity results for several stochastic optimization procedures. Indeed in the recent past, several works have provided improved rates for algorithms like stochastic gradient descent~\cite{needell2014stochastic, ma2018power, bassily2018exponential, gower2019sgd, vaswani2019fast, vaswani2019painless} and sub-sampled Newton's method~\cite{meng2019fast}. In particular, for several settings, the above works demonstrate that the stochastic algorithm may perform as well as the corresponding deterministic counterpart. However, such works only study unconstrained optimization problems and do not have any consequences for constrained stochastic optimization problems of the form in~\eqref{eq:sopt}.

Hence, in this work we consider the following question: \emph{Can we obtain improvements in the oracle complexity of algorithms used for projection-free constrained stochastic optimization problems arising in the context of \textcolor{black}{over-parametrized machine learning models, that are capable of perfectly interpolating the training data}?}  We give a positive answer to the above question by demonstrating that the stochastic conditional gradient method, a projection-free technique for solving constrained stochastic optimization problems, also enjoy improved oracle complexities when they are used to solve constrained stochastic optimization problems of the form in~\eqref{eq:sopt} under certain \emph{interpolation-like} conditions. We elaborate on the specific form of improvement observed below. For stochastic conditional gradient algorithms, the oracle complexity is measured in terms of number of calls to the Stochastic First-order Oracle (SFO) and the Linear Minimization Oracle (LMO) used to the solve the subproblems \textcolor{black}{(that are of the form of minimizing a linear function over the convex feasible set)} arising in the algorithm. \textcolor{black}{In this work, we make the following contribution to the literature on conditional gradient methods under interpolation-like assumptions (see Section~\ref{sec:assumptions} for the exact definitions) on the stochastic gradient:}
\begin{enumerate}[leftmargin=20pt,noitemsep]
\item For the case of convex $f$ in~\eqref{eq:sopt}, we show that the number of calls to the SFO for the \emph{vanilla} stochastic conditional gradient method and stochastic conditional gradient sliding methods are given respectively by $\mathcal{O}(\epsilon^{-2})$ and $\mathcal{O}(\epsilon^{-1.5})$. For comparison, without such assumptions, the corresponding complexities are $\mathcal{O}(\epsilon^{-3})$ and $\mathcal{O}(\epsilon^{-2})$ respectively. The number of calls to the linear minimization oracle (LMO) is of the order $\mathcal{O}(\epsilon^{-1})$, in both cases.
\item We also demonstrate similar improvements in the context of zeroth-order conditional gradient methods, where one only observes noisy evaluations of the function being optimized. Specifically, the number of calls to the stochastic zeroth-order oracle for the \emph{vanilla} stochastic conditional gradient method and stochastic conditional gradient sliding methods are given respectively by $\mathcal{O}(d\epsilon^{-2})$ and $\mathcal{O}(d\epsilon^{-1.5})$, with the same LMO complexity as the first-order setting.
\end{enumerate}
We emphasize that, notably the above improvements are achieved without incorporating any double-loop based existing variance reduction techniques, for example SVRF~\cite{reddi2016stochastic} or SPIDER-FW~\cite{yurtsever2019conditional}. It is also worth noting that ~\cite{defazio2019ineffectiveness,schmidt2020} argue that variance reduction techniques (at the least existing ones) are ineffective in the context of modern deep learning models which are invariably over-parametrized. We also remark that, in contrast to stochastic gradient methods for unconstrained optimization~\cite{vaswani2019fast, bassily2018exponential}, the above improved results  still do not match the corresponding deterministic rates highlighting the subtlety with projection-free optimization. 

\iffalse
\subsection{Related Work}
The conditional gradient method or the Frank-Wolfe method was proposed first by~\cite{frank1956algorithm}. It has obtained renewed interest in the machine learning and optimization communities due to their projection-free nature. We refer the reader to~\cite{jaggi2013revisiting,harchaoui2015conditional, lacoste2015global, beck2017linearly, garber2018fast}, for a partial list of recent works predominantly in the deterministic setting. For the stochastic setting that we consider, in each step of the conditional gradient method, the algorithm requires access to a stochastic first-order oracle (SFO) and a linear minimization oracle (LMO). The complexity of conditional gradient method is hence measured by the number of calls to both oracles. 

\textbf{Convex Setting.} Considering the convex setup,~\cite{hazan2016variance} showed that to obtain an $\epsilon$-optimal point, the number of calls to SFO and LMO are given respectively by $\mathcal{O}(1/\epsilon^{3})$ and $\mathcal{O}(1/\epsilon^{1})$. Furthermore,~\cite{lan2016conditional} proposed Conditional Gradient Sliding (CGS), a modified Frank-Wolfe method by Nesterov's acceleration, that improves the number of calls to the SFO to $\mathcal{O}(1/\epsilon^{3})$ while keeping the number of calls to LMO the same. The above methods require an increasing batch size, in each step, to obtain the above mentioned complexities. Recently,~\cite{mokhtari2018stochastic, hassani2019stochastic, zhang2019one} addressed the issue of increasing batch size. But these works require potentially restrictive assumptions and in particular~\cite{mokhtari2018stochastic} and~\cite{zhang2019one} also require an increased number of calls to the LMO. We highlight that \cite{yurtsever2019conditional} used the SPIDER technique, and showed that one could improve the SFO complexity from $\mathcal{O}(1/\epsilon^{3})$ to $\mathcal{O}(1/\epsilon^{2})$ while mainting the number of calls to the LMO at $\mathcal{O}(1/\epsilon)$. However, to obtain this improved complexities, the SPIDER technique requires double-loop based variance reduction techniques, and hence they are harder to implement in practice compared to the vanilla methods. Furthermore, the SPIDER technique requires the stronger mean-square Lipschitz gradient assumption.

\begin{table*}[t]
\centering
\renewcommand\arraystretch{1.2}
  \begin{tabular}{|l|c|cc|}
    \hline
      & \multirow{2}*{Extra Conditions}	&
      \multicolumn{2}{c|}{First-Order} \\
      & 	&SFO & LMO \\
      \hline
 Vanilla-SFW & 		--	&$\mathcal{O}(\epsilon^{-3})$ & $\mathcal{O} (\epsilon^{-1})$  \\
  SPIDER-SFW & 	Mean-square gradient-smoothness	&$\mathcal{O}(\epsilon^{-2})$ & $\mathcal{O}(\epsilon^{-1})$ \\
  \color{blue}{ Vanilla-SFW} &   	\color{blue}{Interpolation-like}	&\color{blue}{$\mathcal{O}(\epsilon^{-2})$}& \color{blue}{$\mathcal{O}(\epsilon^{-1})$ }\\
  \hline
  Vanilla-SCGS & 		--&$\mathcal{O}(\epsilon^{-2})$ & $\mathcal{O} (\epsilon^{-1})$   \\
    SPIDER-SCGS &   Mean-square gradient-smoothness		&$\mathcal{O}(\epsilon^{-2})$ & $\mathcal{O}(\epsilon^{-1})$  \\
 \color{blue}{Vanilla-SCGS}  &   \color{blue}{Interpolation-like}		&\color{blue}{$\mathcal{O}(\epsilon^{-1.5})$} &\color{blue}{ $\mathcal{O}(\epsilon^{-1})$  }\\
    \hline
  \end{tabular}
  \caption{Comparison of the oracle complexities of conditional gradient methods under various assumptions in the first-order setting. All methods require the gradient-smoothness condition: $\|  \nabla f(x) - \nabla f(y)\|_2 \leq L \|x-y\|$. Mean-square gradient-smoothness refers to $\E_\xi \|  \nabla F(x,\xi) - \nabla F(y,\xi)\|_2^2 \leq L \|x-y\|_2^2$  and is stronger than gradient-smoothness condition. SFO refers to number of calls to the stochastic first order oracle. LMO refers to the number of calls to the linear minimization oracle. The results for vanilla-SFW are from~\cite{hazan2016variance} and~\cite{reddi2016stochastic}. The results for vanilla-SCGS are from~\cite{lan2016conditional}. The results for SPIDER-SFW and SPIDER-SCGS are from~\cite{yurtsever2019conditional}. The results highlighted in blue are our results. Finally, in this work, we also obtain complexities under the zeroth-order setting which are not highlighted in this table, for simplicity. }
\label{tab:comparison}
\end{table*}

\textbf{Comparison to 1-sample SFW from~\cite{zhang2019one}.} While above discussed methods require increasing batch-size with the number of iterations, we highlight that recently~\cite{zhang2019one} proposed 1-sample SFW which does not require increasing batch size. The results in~\cite{zhang2019one} for the 1-sample SFW method has an SFO complexity of $\mathcal{O}(1/\epsilon^{2})$ for the convex setting, the same complexity we present in this work. However, the LMO complexity of 1-sample SFW is $\mathcal{O}(1/\epsilon^{2})$, and they require additional smoothness assumption on $F$. We emphasize that increasing batch size setting is commonly used in the literature of conditional gradient methods and obtaining methods without this requirement under milder assumptions are interesting future work. In this work, we leverage the standard setting of SFW with increasing batch sizes, and focus on the improved oracle complexities of vanilla SFW methods under certain favorable structures.


\textbf{Interpolation.} In the interpolation regime,~\cite{ma2018power} showed that mini-batch stochastic gradient descent (SGD) algorithm enjoys exponential rates of convergence for unconstrained strongly-convex optimization problems; see also~\cite{strohmer2009randomized, needell2014stochastic} for related earlier work. For the non-convex setting, \cite{bassily2018exponential} analyze SGD for non-convex functions satisfying the Polyak-Lojasiewicz (PL) inequality (\cite{polyak1963gradient}) under the interpolation condition and show that SGD can achieve a linear convergence rate. Later, \cite{vaswani2019fast} introduced a more practical form of interpolation condition, and prove that the constant step-size SGD can obtain the optimal convergence rate for strongly-convex and smooth convex functions. They also show the first results in the non-convex setting that the constant step-size SGD can obtain the deterministic rate $\mathcal{O}(1/t)$ in the interpolation regime. Subsequently, \cite{meng2019fast} investigate the regularized subsampled Newton method (R-SSN) and the stochastic BFGS algorithm under the interpolation-like conditions. Very recently,~\cite{roy2020escaping} showed that for non-convex problems, one could escape saddle-points and converge to local-minimizers faster under SGC condition. We emphasize that all the above works consider only unconstrained stochastic optimization problems, while we consider the more challenging constrained stochastic optimization problems.

\fi
{"config": "arxiv", "file": "2006.08167/intro.tex"}