Zero-Order Stochastic Conditional Gradient Sliding Method for Non-smooth Convex Optimization

Understand

The conditional gradient idea proposed by Marguerite Frank and Philip Wolfe in 1956 was so well received by the community that new algorithms (also called Frank--Wolfe type algorithms) are still being actively created.

• In this paper, we study a non-smooth stochastic convex optimization problem with constraints.
• Using a smoothing technique and based on an accelerated batched first-order Stochastic Conditional Gradient Sliding method, we propose a novel gradient-free Frank--Wolfe type algorithm called Zero-Order Stochastic Conditional Gradient Sliding (ZO-SCGS).
• This algorithm is robust not only for the class of non-smooth problems, but surprisingly also for the class of smooth black box problems, outperforming the SOTA algorithms in the smooth case in term oracle calls.