mlsanityData to 7 Oct 2026

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

arXiv 1507.08752 ↗First posted 31 Jul 2015cs.LG math.OC stat.MLcited by 105

Not on the map. Why?

Abstract (arXiv)

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 citedujww13, 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.

Key facts. Cited by 105 papers in the map (data through 7 Oct 2026). First posted on arXiv 31 Jul 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 15; 2022: 14; 2023: 19; 2024: 18; 2025: 16; 2026: 23.

105 papers.

Sort:

By area:

  1. 2023Fine-Tuning Language Models with Just Forward Passescited by 337
  2. 2024Test-Time Model Adaptation with Only Forward Passescited by 74
  3. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  4. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  5. 2022Model Inversion Attacks against Graph Neural Networkscited by 26
  6. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  7. 2023ZO-AdaMU Optimizer: Adapting Perturbation by the Momentum and Uncertainty in Zeroth-order Optimizationcited by 24
  8. 2021Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimizationcited by 21
  9. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 20
  10. 2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 16
  11. 2021Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methodscited by 14
  12. 2021Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descentcited by 14
38 more
  1. 2023Gradient-free optimization of highly smooth functions: improved analysis and a new algorithmcited by 12
  2. 2023Tensor-Compressed Back-Propagation-Free Training for (Physics-Informed) Neural Networkscited by 12
  3. 2023Performative Prediction with Bandit Feedback: Learning through Reparameterizationcited by 11
  4. 2025ComPO: Preference Alignment via Comparison Oraclescited by 11
  5. 2023A Unified Approach for Maximizing Continuous DR-submodular Functionscited by 10
  6. 2024First-Order Methods for Linearly Constrained Bilevel Optimizationcited by 10
  7. 2021Preference learning along multiple criteria: A game-theoretic perspectivecited by 9
  8. 2022Desirable Companion for Vertical Federated Learning: New Zeroth-Order Gradient Based Algorithmcited by 9
  9. 2023Revisiting LQR Control from the Perspective of Receding-Horizon Policy Gradientcited by 9
  10. 2025Perturbation-efficient Zeroth-order Optimization for Hardware-friendly On-device Trainingcited by 9
  11. 2024Improved Regret for Bandit Convex Optimization with Delayed Feedbackcited by 8
  12. 2024Private Zeroth-Order Nonsmooth Nonconvex Optimizationcited by 8
  13. 2022A gradient estimator via L1-randomization for online zero-order optimization with two point feedbackcited by 7
  14. 2023Federated Online and Bandit Convex Optimizationcited by 7
  15. 2025Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimizationcited by 7
  16. 2021Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithmcited by 6
  17. 2021Optimum-statistical Collaboration Towards General and Efficient Black-box Optimizationcited by 6
  18. 2025Zeroth-Order Optimization Finds Flat Minimacited by 6
  19. 2021Smoothed functional-based gradient algorithms for off-policy reinforcement learning: A non-asymptotic viewpointcited by 5
  20. 2024Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimizationcited by 5
  21. 2026Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variationscited by 5
  22. 2021SGD with Coordinate Sampling: Theory and Practicecited by 4
  23. 2021Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descentcited by 4
  24. 2021Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimizationcited by 4
  25. 2021Fast rates for prediction with limited expert advicecited by 4
  26. 2022Faster online calibration without randomization: interval forecasts and the power of two choicescited by 4
  27. 2023PyXAB -- A Python Library for X-Armed Bandit and Online Blackbox Optimization Algorithmscited by 4
  28. 2024A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimizationcited by 4
  29. 2024Improved Sample Complexity for Private Nonsmooth Nonconvex Optimizationcited by 4
  30. 2025A First-order Generative Bilevel Optimization Framework for Diffusion Modelscited by 4
  31. 2025SUA: Stealthy Multimodal Large Language Model Unlearning Attackcited by 4
  32. 2021Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimizationcited by 3
  33. 2021Decentralized Multi-Task Stochastic Optimization With Compressed Communicationscited by 3
  34. 2022Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivitycited by 3
  35. 2023Gradient is All You Need? How Consensus-Based Optimization can be Interpreted as a Stochastic Relaxation of Gradient Descentcited by 3
  36. 2024Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimizationcited by 3
  37. 2026A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guaranteescited by 3
  38. 2022A policy gradient approach for optimization of smooth risk measurescited by 2

50 most cited of 105 All 105 (JSON)