Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithm on Stochastic Smooth Functions

2025/12/22 by Haishan Ye, Ye, Haishan
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Age of Information Optimization #Reinforcement Learning in Robotics

paper · doi:10.48550/arxiv.2512.19104

Abstract

Zeroth-order (ZO) optimization with ordinal feedback has emerged as a fundamental problem in modern machine learning systems, particularly in human-in-the-loop settings such as reinforcement learning from human feedback, preference learning, and evolutionary strategies. While rank-based ZO algorithms enjoy strong empirical success and robustness properties, their theoretical understanding, especially under stochastic objectives and standard smoothness assumptions, remains limited. In this paper, we study rank-based zeroth-order optimization for stochastic functions where only ordinal feedback of the stochastic function is available. We propose a simple and computationally efficient rank-based ZO algorithm. Under standard assumptions including smoothness, strong convexity, and bounded second moments of stochastic gradients, we establish explicit non-asymptotic query complexity bounds for both convex and nonconvex objectives. Notably, our results match the best-known query complexities of value-based ZO algorithms, demonstrating that ordinal information alone is sufficient for optimal query efficiency in stochastic settings. Our analysis departs from existing drift-based and information-geometric techniques, offering new tools for the study of rank-based optimization under noise. These findings narrow the gap between theory and practice and provide a principled foundation for optimization driven by human preferences.

Citations

• Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithms on Smooth Functions
• Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles
• Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons
• Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback
• Training language models to follow instructions with human feedback
• Regret Analysis for Continuous Dueling Bandit
• Optimization Methods for Large-Scale Machine Learning
• Optimization Methods for Large-Scale Machine Learning
• The CMA Evolution Strategy: A Tutorial
• CMA-ES for Hyperparameter Optimization of Deep Neural Networks
• Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization

Related

• Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithms on Smooth Functions
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity
• Stochastic Zeroth-order Functional Constrained Optimization: Oracle Complexity and Applications
• Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles