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

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.

• Publication year

  2015

• Venue

  Journal of machine learning research

• Publication date

  2015-07-31

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1507.08752
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Random Gradient-Free Minimization of Convex Functions

  2015cited by this paper
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming

  2013cited by this paper
• Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations

  2013cited by this paper
• Optimal rates for zero-order optimization: the power of two function evaluations

  2013influential reference
• Online Learning and Online Convex Optimization

  2012cited by this paper
• Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.

  2010influential reference
• Online learning: theory, algorithms and applications (למידה מקוונת.)

  2007cited by this paper
• Logarithmic regret algorithms for online convex optimization

  2006cited by this paper
• Online convex optimization in the bandit setting: gradient descent without a gradient

  2004cited by this paper
• The concentration of measure phenomenon

  2001cited by this paper
• On the generalization ability of on-line learning algorithms

  2001cited by this paper

• Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations

  2026cites this paper
• ZIVR: An Incremental Variance Reduction Technique For Zeroth-Order Composite Problems

  2026cites this paper
• Convex and Non-convex Federated Learning with Stale Stochastic Gradients: Diminishing Step Size is All You Need

  2026cites this paper
• Guiding the Recommender: Information-Aware Auto-Bidding for Content Promotion

  2026cites this paper
• Probabilistic Taylor-Type Expansions of Functions

  2026cites this paper
• Small Gradient Norm Regret for Online Convex Optimization

  2026cites this paper
• A Derivative-Free Saddle-search Algorithm With Linear Convergence Rate

  2026cites this paper
• Decentralized Nonsmooth Nonconvex Optimization with Client Sampling

  2026cites this paper
• Zeroth-order methods for non-smooth stochastic problems under heavy-tailed noise

  2026cites this paper
• A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees

  2026influential citation
• Deterministic Zeroth-Order Mirror Descent via Vector Fields with A Posteriori Certification

  2026cites this paper
• Escaping from saddle points with perturbed gradient estimation

  2026cites this paper
• Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity

  2026cites this paper
• A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization

  2025influential citation
• VAMO: Efficient Zeroth-Order Variance Reduction for SGD with Faster Convergence

  2025cites this paper
• ComPO: Preference Alignment via Comparison Oracles

  2025cites this paper
• One-Point Sampling for Distributed Bandit Convex Optimization With Time-Varying Constraints

  2025cites this paper
• A First-order Generative Bilevel Optimization Framework for Diffusion Models

  2025cites this paper
• Efficient Federated Fine-Tuning via Zeroth-Order Optimization for Resource-Constrained Edge Devices

  2025cites this paper
• A Structured Tour of Optimization with Finite Differences

  2025cites this paper
• A Structured Proximal Stochastic Variance Reduced Zeroth-order Algorithm

  2025cites this paper
• Duality and Policy Evaluation in Distributionally Robust Bayesian Diffusion Control

  2025cites this paper
• Two-point Random Gradient-free Methods for Model-free Feedback Optimization

  2025influential citation
• Dimension-Free Estimators of Gradients of Functions with(out) Non-Independent Variables

  2025influential citation
• Perturbation-efficient Zeroth-order Optimization for Hardware-friendly On-device Training

  2025cites this paper
• Distributed Stochastic Zeroth-Order Optimization With Compressed Communication

  2025cites this paper
• High-Probability Analysis of Online and Federated Zero-Order Optimisation

  2025cites this paper
• Zeroth-Order Sharpness-Aware Learning with Exponential Tilting

  2025cites this paper
• Inexact zeroth-order nonsmooth and nonconvex stochastic composite optimization and applications

  2025influential citation
• Scalable Back-Propagation-Free Training of Optical Physics-Informed Neural Networks

  2025cites this paper
• Communication-Efficient and Differentially Private Vertical Federated Learning with Zeroth-Order Optimization

  2025cites this paper
• Solving Infinite-Player Games with Player-to-Strategy Networks

  2025cites this paper
• On the Almost Sure Convergence of the Stochastic Three Points Algorithm

  2025cites this paper
• Zeroth-Order Optimization Finds Flat Minima

  2025cites this paper
• Differential Privacy Decentralized Federated Learning for Internet of Vehicles Over Time-Varying Unbalanced Networks

  2025cites this paper
• Revisiting Randomized Smoothing: Nonsmooth Nonconvex Optimization Beyond Global Lipschitz Continuity

  2025cites this paper
• Achieve Performatively Optimal Policy for Performative Reinforcement Learning

  2025cites this paper
• Multi-Objective min-max Online Convex Optimization

  2025cites this paper
• Preference-based optimization from noisy pairwise comparisons

  2025influential citation
• ConMeZO: Adaptive Descent-Direction Sampling for Gradient-Free Finetuning of Large Language Models

  2025cites this paper
• On the Robustness of Derivative-free Methods for Linear Quadratic Regulator

  2025cites this paper
• SUA: Stealthy Multimodal Large Language Model Unlearning Attack

  2025cites this paper
• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization

  2025cites this paper
• Power of Generalized Smoothness in Stochastic Convex Optimization: First- and Zero-Order Algorithms

  2025cites this paper
• Process-Based Triggering and Accelerated Dual Averaging Algorithm for Dynamic Parameter Estimation

  2025cites this paper
• Non-Stationary Bandit Convex Optimization: An Optimal Algorithm with Two-Point Feedback

  2025influential citation
• Communication-Efficient Distributed Online Nonconvex Optimization with Time-Varying Constraints

  2025cites this paper
• Online Feedback Optimization over Networks: A Distributed Model-free Approach

  2024cites this paper
• Highly Smooth Zeroth-Order Methods for Solving Optimization Problems under the PL Condition

  2024cites this paper
• AlphaZeroES: Direct score maximization outperforms planning loss minimization

  2024cites this paper
• Simultaneous incremental support adjustment and metagame solving: An equilibrium-finding framework for continuous-action games

  2024cites this paper
• Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization

  2024cites this paper
• A General Framework for Approximate and Delayed Gradient Descent for Decomposable Cost Functions

  2024cites this paper
• Private Zeroth-Order Nonsmooth Nonconvex Optimization

  2024cites this paper
• Stochastic Two Points Method for Deep Model Zeroth-order Optimization

  2024cites this paper
• First-Order Methods for Linearly Constrained Bilevel Optimization

  2024cites this paper
• Mollification Effects of Policy Gradient Methods

  2024cites this paper
• Zero Order Algorithm for Decentralized Optimization Problems

  2024cites this paper
• Test-Time Model Adaptation with Only Forward Passes

  2024cites this paper
• Zeroth-Order Decentralized Dual Averaging for Online Optimization With Privacy Consideration

  2024cites this paper
• Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional Optimization

  2024cites this paper
• Improved Regret for Bandit Convex Optimization with Delayed Feedback

  2024cites this paper
• Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization

  2024cites this paper
• Federated Learning Can Find Friends That Are Beneficial

  2024cites this paper
• Dynamic Anisotropic Smoothing for Noisy Derivative-Free Optimization

  2024cites this paper
• Zeroth-Order Feedback Optimization for Inverter-Based Volt-VAR Control in Wind Farm

  2024cites this paper
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime

  2024cites this paper
• Differentially private distributed online optimization via push-sum one-point bandit dual averaging

  2024cites this paper
• Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi-Armed Bandit Problem with Heavy-tailed Symmetric Noise

  2024cites this paper
• Event-Triggered Proximal Online Gradient Descent Algorithm for Parameter Estimation

  2024cites this paper
• Reduced Network Cumulative Constraint Violation for Distributed Bandit Convex Optimization under Slater Condition

  2024cites this paper
• Privacy Preserving Distributed Bandit Residual Feedback Online Optimization Over Time-Varying Unbalanced Graphs

  2024cites this paper
• Zeroth-Order Feedback Optimization in Multi-Agent Systems: Tackling Coupled Constraints

  2024cites this paper
• Distributed zeroth-order optimization: Convergence rates that match centralized counterpart

  2024cites this paper
• PyXAB - A Python Library for \mathcal{X}-Armed Bandit and Online Blackbox Optimization Algorithms

  2024cites this paper
• Risk-averse learning with delayed feedback

  2024cites this paper
• Quantum Algorithm for Online Exp-concave Optimization

  2024cites this paper
• Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization

  2024cites this paper
• Joint-perturbation simultaneous pseudo-gradient

  2024cites this paper
• Gradient-Free Accelerated Event-Triggered Scheme for Constrained Network Optimization in Smart Grids

  2024cites this paper
• New aspects of black box conditional gradient: Variance reduction and one point feedback

  2024cites this paper
• A New Formulation for Zeroth-Order Optimization of Adversarial EXEmples in Malware Detection

  2024cites this paper
• Zeroth-Order Katyusha: An Accelerated Derivative-Free Method for Composite Convex Optimization

  2024cites this paper
• Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret

  2024influential citation
• Zeroth-Order Random Subspace Algorithm for Non-smooth Convex Optimization

  2024influential citation
• An Inexact Preconditioned Zeroth-Order Proximal Method for Composite Optimization

  2024cites this paper
• Federated Learning Can Find Friends That Are Advantageous

  2024cites this paper
• Online Convex Optimization with Memory and Limited Predictions

  2024cites this paper
• A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization

  2024cites this paper
• Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values

  2024cites this paper
• Online Nonconvex Optimization with Limited Instantaneous Oracle Feedback

  2023cites this paper
• Constrained Global Optimization by Smoothing

  2023influential citation
• Planning in the imagination: High-level planning on learned abstract search spaces

  2023cites this paper
• Federated Online and Bandit Convex Optimization

  2023influential citation
• Accelerated Zero-Order SGD Method for Solving the Black Box Optimization Problem Under "Overparametrization" Condition

  2023influential citation
• Computing equilibria by minimizing exploitability with best-response ensembles

  2023cites this paper
• Non-smooth setting of stochastic decentralized convex optimization problem over time-varying Graphs

  2023cites this paper
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization

  2023cites this paper
• AI planning in the imagination: High-level planning on learned abstract search spaces

  2023cites this paper
• SelfTune: Tuning Cluster Managers

  2023cites this paper