In this paper, we consider the general non-oblivious stochastic optimization
where the underlying stochasticity may change during the optimization procedure
and depends on the point at which the function is evaluated. We develop
Stochastic Frank-Wolfe++ ($\text{SFW}{++} $), an efficient variant of the
conditional gradient method for minimizing a smooth non-convex function subject
to a convex body constraint. We show that $\text{SFW}{++} $ converges to an
$\epsilon$-first order stationary point by using $O(1/\epsilon^3)$ stochastic
gradients. Once further structures are present, $\text{SFW}{++}$'s theoretical
guarantees, in terms of the convergence rate and quality of its solution,
improve. In particular, for minimizing a convex function, $\text{SFW}{++} $
achieves an $\epsilon$-approximate optimum while using $O(1/\epsilon^2)$
stochastic gradients. It is known that this rate is optimal in terms of
stochastic gradient evaluations. Similarly, for maximizing a monotone
continuous DR-submodular function, a slightly different form of $\text{SFW}{++}
$, called Stochastic Continuous Greedy++ ($\text{SCG}{++} $), achieves a tight
$[(1-1/e)\text{OPT} -\epsilon]$ solution while using $O(1/\epsilon^2)$
stochastic gradients. Through an information theoretic argument, we also prove
that $\text{SCG}{++} $'s convergence rate is optimal. Finally, for maximizing a
non-monotone continuous DR-submodular function, we can achieve a
$[(1/e)\text{OPT} -\epsilon]$ solution by using $O(1/\epsilon^2)$ stochastic
gradients. We should highlight that our results and our novel variance
reduction technique trivially extend to the standard and easier oblivious
stochastic optimization settings for (non-)covex and continuous submodular
settings.

本文提出了一种用于非显式随机优化问题的算法 SFW ++，使用该算法可以快速收敛于全局最优解，并通过一些简单的结构扩展，可以优化跨不同优化问题的条件梯度方法。

随机条件梯度 ++

Stochastic Conditional Gradient++

In this paper, we study the problem of \textit{constrained} and
\textit{stochastic} continuous submodular maximization. Even though the
objective function is not concave (nor convex) and is defined in terms of an
expectation, we develop a variant of the conditional gradient method, called
\alg, which achieves a \textit{tight} approximation guarantee. More precisely,
for a monotone and continuous DR-submodular function and subject to a
\textit{general} convex body constraint, we prove that \alg achieves a
$[(1-1/e)\text{OPT} -\eps]$ guarantee (in expectation) with
$\mathcal{O}{(1/\eps^3)}$ stochastic gradient computations. This guarantee
matches the known hardness results and closes the gap between deterministic and
stochastic continuous submodular maximization. By using stochastic continuous
optimization as an interface, we also provide the first $(1-1/e)$ tight
approximation guarantee for maximizing a \textit{monotone but stochastic}
submodular \textit{set} function subject to a general matroid constraint.

研究连续子模最大化问题，通过提供新颖的算法并使用随机持续优化作为接口，在满足约束条件的情况下获得了紧密的逼近保证。