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 (15)

• 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
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• SEGA: Variance Reduction via Gradient Sketching
• An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization
• Derivative-Free Method For Composite Optimization With Applications To Decentralized Distributed Optimization
• 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
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features
• Ancestral Reinforcement Learning: Unifying Zeroth-Order Optimization and Genetic Algorithms for Reinforcement Learning
• Zeroth-Order Actor-Critic: An Evolutionary Framework for Sequential Decision Problems