An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback

Abstract

We consider the closely related problems of bandit convex optimization with two-point feedback, and zero-order stochastic convex optimization with two function evaluations per round. We provide a simple algorithm and analysis which is optimal for convex Lipschitz functions. This improves on \cite{dujww13}, which only provides an optimal result for smooth functions; Moreover, the algorithm and analysis are simpler, and readily extend to non-Euclidean problems. The algorithm is based on a small but surprisingly powerful modification of the gradient estimator.

9 pages

Cited by in corpus (63)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Bandit Convex Optimization for Scalable and Dynamic IoT Management
• Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization
• Gradientless Descent: High-Dimensional Zeroth-Order Optimization
• Model-Free Nonlinear Feedback Optimization
• Distributed Online Optimization in Time-Varying Unbalanced Networks without Explicit Subgradients
• An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization
• Recent theoretical advances in decentralized distributed convex optimization
• Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attack
• Universal gradient descent
• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Distributed Online Linear Regression
• Optimization and Supervised Machine Learning Methods for Fitting Numerical Physics Models without Derivatives
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Bandit Convex Optimization in Non-stationary Environments
• Compositional ADAM: An Adaptive Compositional Solver
• Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints
• Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems
• Desirable Companion for Vertical Federated Learning: New Zeroth-Order Gradient Based Algorithm
• Distributed Zero-Order Algorithms for Nonconvex Multi-Agent Optimization
• Gradient-free two-points optimal method for non smooth stochastic convex optimization problem with additional small noise
• Decentralized Markov Chain Gradient Descent
• Improved Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandit
• Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization
• Distributed Zero-Order Optimization under Adversarial Noise
• A New One-Point Residual-Feedback Oracle For Black-Box Learning and Control
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework
• Improve Single-Point Zeroth-Order Optimization Using High-Pass and Low-Pass Filters
• On the upper bound for the mathematical expectation of the norm of a vector uniformly distributed on the sphere and the phenomenon of concentration of uniform measure on the sphere
• Black Box Submodular Maximization: Discrete and Continuous Settings
• A Frank-Wolfe Framework for Efficient and Effective Adversarial Attacks
• Distributed Mirror Descent for Online Composite Optimization
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks
• Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods
• Searching equillibriums in large transport networks
• The Minimax Complexity of Distributed Optimization
• SGD with Coordinate Sampling: Theory and Practice
• Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent
• Asymptotic proximal point methods: finding the global minima with linear convergence for a class of multiple minima problems
• Non-stationary Stochastic Optimization under $L_{p,q}$-Variation Measures
• Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization
• Linearly Convergent Gradient-Free Methods for Minimization of Parabolic Approximation
• Parallel and Distributed algorithms for ML problems
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm
• Small errors in random zeroth-order optimization are imaginary
• Zeroth-Order Feedback Optimization for Cooperative Multi-Agent Systems
• Programming by Rewards
• Optimization with Zeroth-Order Oracles in Formation
• Stochastic gradient-free descents
• Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization
• Quantum Algorithm for Online Convex Optimization
• New Aspects of Black Box Conditional Gradient: Variance Reduction and One Point Feedback
• Scalable Projection-Free Optimization
• One-Point Feedback for Composite Optimization with Applications to Distributed and Federated Learning
• Algorithmic models of human behavior and stochastic optimization
• Derivative-free global minimization for a class of multiple minima problems
• Graduated Optimization of Black-Box Functions
• Minimizing Regret of Bandit Online Optimization in Unconstrained Action Spaces