Stochastic Conditional Gradient++

Abstract

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.

References in corpus (12)

• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives
• Near-Optimally Teaching the Crowd to Classify
• Variance-Reduced and Projection-Free Stochastic Optimization
• Projection-free Online Learning
• Online Continuous Submodular Maximization
• Escaping Saddle Points in Constrained Optimization
• Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
• Conditional Accelerated Lazy Stochastic Gradient Descent
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points

Cited by in corpus (7)

• One Sample Stochastic Frank-Wolfe
• Safe Learning under Uncertain Objectives and Constraints
• Faster Projection-free Online Learning
• Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning
• Efficient Projection-Free Algorithms for Saddle Point Problems
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step
• Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions