Sparse Stochastic Zeroth-Order Optimization with an Application to Bandit Structured Prediction

Abstract

Stochastic zeroth-order (SZO), or gradient-free, optimization allows to optimize arbitrary functions by relying only on function evaluations under parameter perturbations, however, the iteration complexity of SZO methods suffers a factor proportional to the dimensionality of the perturbed function. We show that in scenarios with natural sparsity patterns as in structured prediction applications, this factor can be reduced to the expected number of active features over input-output pairs. We give a general proof that applies sparse SZO optimization to Lipschitz-continuous, nonconvex, stochastic objectives, and present an experimental evaluation on linear bandit structured prediction tasks with sparse word-based feature representations that confirm our theoretical results.

References in corpus (6)

• Auto-Encoding Variational Bayes
• Categorical Reparameterization with Gumbel-Softmax
• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• An Actor-Critic Algorithm for Sequence Prediction
• Simple random search provides a competitive approach to reinforcement learning
• Stochastic Structured Prediction under Bandit Feedback

Cited by in corpus (2)

• Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization
• Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization