New Aspects of Black Box Conditional Gradient: Variance Reduction and One Point Feedback

Abstract

This paper deals with the black-box optimization problem. In this setup, we do not have access to the gradient of the objective function, therefore, we need to estimate it somehow. We propose a new type of approximation JAGUAR, that memorizes information from previous iterations and requires $\mathcal{O}(1)$ oracle calls. We implement this approximation in the Frank-Wolfe and Gradient Descent algorithms and prove the convergence of these methods with different types of zero-order oracle. Our theoretical analysis covers scenarios of non-convex, convex and PL-condition cases. Also in this paper, we consider the stochastic minimization problem on the set $Q$ with noise in the zero-order oracle; this setup is quite unpopular in the literature, but we prove that the JAGUAR approximation is robust not only in deterministic minimization problems, but also in the stochastic case. We perform experiments to compare our gradient estimator with those already known in the literature and confirm the dominance of our methods.

29 pages, 5 algorithms, 3 figures, 1 table

References in corpus (10)

• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Randomized gradient-free methods in convex optimization
• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization
• Non-Smooth Setting of Stochastic Decentralized Convex Optimization Problem Over Time-Varying Graphs
• A gradient estimator via L1-randomization for online zero-order optimization with two point feedback
• Gradient-free algorithm for saddle point problems under overparametrization
• Ancestral Reinforcement Learning: Unifying Zeroth-Order Optimization and Genetic Algorithms for Reinforcement Learning
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features
• Zeroth-Order Actor-Critic: An Evolutionary Framework for Sequential Decision Problems